Виды алгоритмов сортировки Сортировка пузырьком / Bubble sort

Пример реализации на Kotlin

жүктеу/скачать 121,16 Kb.

бет	6/12
Дата	16.10.2023
өлшемі	121,16 Kb.
	#115872

1 2 3 4 5 6 7 8 9 ... 12

Байланысты:
Виды алгоритмов сортировки

Пример реализации на Kotlin:
fun sort(arr: IntArray): Int {
val n = arr.size
var gap = n / 2
while (gap > 0) {
var i = gap
while (i < n) {
val temp = arr[i]
var j = i
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap]
j -= gap
}
arr[j] = temp
i += 1
}
gap /= 2
}
return 0
}
Псевдокод
ЗАДАЧА Шелл(a=: РЯД ИЗ ЦЕЛ);
ПЕР
b,i,j,k,h: ЦЕЛ;
УКАЗ
b:=РАЗМЕР(a);
k:=b ДЕЛИТЬ 2;
ПОКА k>0 ВЫП
ОТ i:=1 ДО b-k ВЫП
j:=i;
ПОКА (j>=1) И (a[j]>a[j+k]) ВЫП
h:=a[j];
a[j]:=a[j+k];
a[j+k]:=h;
УМЕНЬШИТЬ(j);
КОН;
КОН;
k:=k ДЕЛИТЬ 2
КОН
КОН Шелл;
Реализация на Python
def shell(seq):
inc = len(seq) // 2
while inc:
for i, el in enumerate(seq):
while i >= inc and seq[i - inc] > el:
seq[i] = seq[i - inc]
i -= inc
seq[i] = el
inc = 1 if inc == 2 else int(inc * 5.0 / 11)
data = [22, 7, 2, -5, 8, 4]
shell(data)
print (data)
# [-5, 2, 4, 7, 8, 22]

Сложность	Лучшее	Среднее	Худшее
Время	O(n log n)	зависит от выбранных шагов (d)	O(n²) или O(n log² n) (зависит от выбранных шагов)
Память			O(1)

Сортировка выбором / Selection Sort
Сортировка выбором - это алгоритм, при котором многократно осуществляется поиск минимального элемента в неотсортированной части массива и его помещение в конец отсортированной части массива.
Общая идея алгоритма:

Данный алгоритм условно делит массив на две части:
- подмассив, который уже отсортирован (находится в левой части массива),
- подмассив, который нужно отсортировать (находится в правой части массива).
Поиск минимального значения в неотсортированном массиве. Найденное значение меняем местами с первым элементом в неотсортированном массиве.
Повторяем предыдущий шаг до тех пор, пока массив не будет отсортирован.

Пример реализации на Kotlin:

	fun selectionSort(sampleArray: IntArray) { var n = sampleArray.size var temp: Int for(i in 0..n-1) { var indexOfMin = i for(j in n-1 downTo i) { if (sampleArray[j] < sampleArray[indexOfMin]) indexOfMin=j } if (i != indexOfMin) { temp = sampleArray[i] sampleArray[i] = sampleArray[indexOfMin] sampleArray[indexOfMin] = temp } } }
Сложность	Лучшее	Среднее	Худшее
Время	O(n²)	O(n²)	O(n²)
Память			O(1)

Быстрая сортировка / Quick Sort
Быстрая сортировка - это алгоритм типа “разделяй и властвуй”.
Общая идея алгоритма:

Выбрать из массива элемент, который обычно называют опорным. Это может быть любой элемент из массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность.
Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие».
Рекурсивно применить первые два шага к отрезкам, содержащим «меньшие» и «большие» значения. Не применять к массиву, в котором только один элемент или отсутствуют элементы.

Пример реализации на Kotlin:

	fun quicksort(items: List): List { // если в массиве меньше 2х элементов, то он уже отсортирован if (items.count() < 2) { return items } // выбираем опорный элемент val pivot = items[items.count()/2] // сортируем элементы по 3м массивам - меньшие, равные и большие опорного val equal = items.filter { it == pivot } val less = items.filter { it < pivot } val greater = items.filter { it > pivot } // рекурсивно вызываем функцию для меньших и больших элементов return quicksort(less) + equal + quicksort(greater) }

жүктеу/скачать 121,16 Kb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7 8 9 ... 12