Рассматриваются методы сортировки (алгоритмы).
В языке Python имеется функция sorted() и метод sort() применимый к спискам, но эта статья не об этом.
>>> a = [5, 3, 1, 4]
>>> a.sort()
>>> print(a)
[1, 3, 4, 5]Мы займёмся изучением алгоритмов сортировки.
Алгоритм сортировки — это алгоритм для упорядочивания элементов в массиве (списке).
1. Метод сортировки — «Сортировка вставкой»
def mySort(array):
for i in range(1, len(array)):
while (i > 0 and array[i] < array[i-1]):
array[i], array[i-1] = array[i-1], array[i]
i -= 1
return array
a = [7, 5, 3, 1, 4, 9, 3, 2]
print(mySort(a))Программа 1, реализующая сортировку «вставкой».
Результат:
[1, 2, 3, 3, 4, 5, 7, 9]Метод сортировки вставкой (insertion sort) заключается в выборе элемента из списка следующего за отсортированной частью списка и вставке этого элемента в соответствующую позицию в отсортированной части списка. Отсортированная часть списка изначально состоит из первого элемента списка.
Алгоритм сортирует элементы непосредственно в исходном списке, поэтому он не требователен к ресурсам памяти.
Производительность алгоритма O(N2)
Список до сортировки: [7, 5, 3, 1, 4, 9, 3, 2]
Порядковый номер элемента в списке i = 1
Значение array[i] = 5
[5, 7, 3, 1, 4, 9, 3, 2]
Порядковый номер элемента в списке i = 2
Значение array[i] = 3
[5, 3, 7, 1, 4, 9, 3, 2]
[3, 5, 7, 1, 4, 9, 3, 2]
Порядковый номер элемента в списке i = 3
Значение array[i] = 1
[3, 5, 1, 7, 4, 9, 3, 2]
[3, 1, 5, 7, 4, 9, 3, 2]
[1, 3, 5, 7, 4, 9, 3, 2]
Порядковый номер элемента в списке i = 4
Значение array[i] = 4
[1, 3, 5, 4, 7, 9, 3, 2]
[1, 3, 4, 5, 7, 9, 3, 2]
Порядковый номер элемента в списке i = 5
Значение array[i] = 9
Порядковый номер элемента в списке i = 6
Значение array[i] = 3
[1, 3, 4, 5, 7, 3, 9, 2]
[1, 3, 4, 5, 3, 7, 9, 2]
[1, 3, 4, 3, 5, 7, 9, 2]
[1, 3, 3, 4, 5, 7, 9, 2]
Порядковый номер элемента в списке i = 7
Значение array[i] = 2
[1, 3, 3, 4, 5, 7, 2, 9]
[1, 3, 3, 4, 5, 2, 7, 9]
[1, 3, 3, 4, 2, 5, 7, 9]
[1, 3, 3, 2, 4, 5, 7, 9]
[1, 3, 2, 3, 4, 5, 7, 9]
[1, 2, 3, 3, 4, 5, 7, 9]
Список после сортировки: [1, 2, 3, 3, 4, 5, 7, 9]Листинг 1. Процесс сортировки методом «Сортировка вставкой».
2. Метод сортировки — «Сортировка выбором»
def mySort(array):
for i in range(0, len(array)):
for n in range(i+1, len(array)):
if (array[n] < array[i]):
array[n], array[i] = array[i], array[n]
return array
a = [7, 5, 3, 1, 4, 9, 3, 2]
print(mySort(a))Программа 2, реализующая сортировку «выбором».
Результат:
[1, 2, 3, 3, 4, 5, 7, 9]Суть сортировки выбором (selection sort) состоит в том, чтобы найти в не отсортированной части списка наименьший элемент и поменять его местами с первым элементом, следующим за отсортированной частью списка. В начале отсортированная часть списка пуста, ищем наименьший элемент списка и меняем его с первым элементом списка местами.
Алгоритм сортирует элементы непосредственно в исходном списке, поэтому он не требователен к ресурсам памяти.
Производительность алгоритма O(N2)
Список отсортирован до элемента: 0 [7, 5, 3, 1, 4, 9, 3, 2]
Цикл № 0 Сравниваем: 7 5
Цикл № 1 Сравниваем: 5 3
Цикл № 2 Сравниваем: 3 1
Цикл № 3 Сравниваем: 1 4
Цикл № 4 Сравниваем: 1 9
Цикл № 5 Сравниваем: 1 3
Цикл № 6 Сравниваем: 1 2
Список отсортирован до элемента: 1 [1, 7, 5, 3, 4, 9, 3, 2]
Цикл № 7 Сравниваем: 7 5
Цикл № 8 Сравниваем: 5 3
Цикл № 9 Сравниваем: 3 4
Цикл № 10 Сравниваем: 3 9
Цикл № 11 Сравниваем: 3 3
Цикл № 12 Сравниваем: 3 2
Список отсортирован до элемента: 2 [1, 2, 7, 5, 4, 9, 3, 3]
Цикл № 13 Сравниваем: 7 5
Цикл № 14 Сравниваем: 5 4
Цикл № 15 Сравниваем: 4 9
Цикл № 16 Сравниваем: 4 3
Цикл № 17 Сравниваем: 3 3
Список отсортирован до элемента: 3 [1, 2, 3, 7, 5, 9, 4, 3]
Цикл № 18 Сравниваем: 7 5
Цикл № 19 Сравниваем: 5 9
Цикл № 20 Сравниваем: 5 4
Цикл № 21 Сравниваем: 4 3
Список отсортирован до элемента: 4 [1, 2, 3, 3, 7, 9, 5, 4]
Цикл № 22 Сравниваем: 7 9
Цикл № 23 Сравниваем: 7 5
Цикл № 24 Сравниваем: 5 4
Список отсортирован до элемента: 5 [1, 2, 3, 3, 4, 9, 7, 5]
Цикл № 25 Сравниваем: 9 7
Цикл № 26 Сравниваем: 7 5
Список отсортирован до элемента: 6 [1, 2, 3, 3, 4, 5, 9, 7]
Цикл № 27 Сравниваем: 9 7
Список отсортирован до элемента: 7 [1, 2, 3, 3, 4, 5, 7, 9]
[1, 2, 3, 3, 4, 5, 7, 9]Листинг 2. Процесс сортировки методом «Сортировка выбором».
3. Метод сортировки «Сортировка методом пузырька»
def mySort(array):
noSorted = True
while noSorted:
noSorted = False
for i in range(0, len(array)-1):
if (array[i] > array[i+1]):
noSorted = True
array[i], array[i+1] = array[i+1], array[i]
return array
a = [7, 5, 3, 1, 4, 9, 3, 2]
print(mySort(a))Программа 3, реализующая сортировку «методом пузырька».
Результат:
[1, 2, 3, 3, 4, 5, 7, 9]Сортировка методом пузырька (bubble sort) выполняется исходя из предположения, что в не отсортированном списке всегда найдётся два смежных элемента, которые находятся в неправильном положении. Из-за этого алгоритм должен проходить по массиву несколько раз, меняя местами все неправильные пары. Заканчивается сортировка тогда, когда алгоритм за проход по списку от начала до конца не находит ни одной неправильной пары.
Производительность алгоритма O(N2).
Не отсортированный массив: [7, 5, 3, 1, 4, 9, 3, 2]
Цикл № 0 Сравниваются: 7 5
Упорядочена ещё одна пара: [5, 7, 3, 1, 4, 9, 3, 2]
Цикл № 1 Сравниваются: 7 3
Упорядочена ещё одна пара: [5, 3, 7, 1, 4, 9, 3, 2]
Цикл № 2 Сравниваются: 7 1
Упорядочена ещё одна пара: [5, 3, 1, 7, 4, 9, 3, 2]
Цикл № 3 Сравниваются: 7 4
Упорядочена ещё одна пара: [5, 3, 1, 4, 7, 9, 3, 2]
Цикл № 4 Сравниваются: 7 9
Цикл № 5 Сравниваются: 9 3
Упорядочена ещё одна пара: [5, 3, 1, 4, 7, 3, 9, 2]
Цикл № 6 Сравниваются: 9 2
Упорядочена ещё одна пара: [5, 3, 1, 4, 7, 3, 2, 9]
Цикл № 7 Сравниваются: 5 3
Упорядочена ещё одна пара: [3, 5, 1, 4, 7, 3, 2, 9]
Цикл № 8 Сравниваются: 5 1
Упорядочена ещё одна пара: [3, 1, 5, 4, 7, 3, 2, 9]
Цикл № 9 Сравниваются: 5 4
Упорядочена ещё одна пара: [3, 1, 4, 5, 7, 3, 2, 9]
Цикл № 10 Сравниваются: 5 7
Цикл № 11 Сравниваются: 7 3
Упорядочена ещё одна пара: [3, 1, 4, 5, 3, 7, 2, 9]
Цикл № 12 Сравниваются: 7 2
Упорядочена ещё одна пара: [3, 1, 4, 5, 3, 2, 7, 9]
Цикл № 13 Сравниваются: 7 9
Цикл № 14 Сравниваются: 3 1
Упорядочена ещё одна пара: [1, 3, 4, 5, 3, 2, 7, 9]
Цикл № 15 Сравниваются: 3 4
Цикл № 16 Сравниваются: 4 5
Цикл № 17 Сравниваются: 5 3
Упорядочена ещё одна пара: [1, 3, 4, 3, 5, 2, 7, 9]
Цикл № 18 Сравниваются: 5 2
Упорядочена ещё одна пара: [1, 3, 4, 3, 2, 5, 7, 9]
Цикл № 19 Сравниваются: 5 7
Цикл № 20 Сравниваются: 7 9
Цикл № 21 Сравниваются: 1 3
Цикл № 22 Сравниваются: 3 4
Цикл № 23 Сравниваются: 4 3
Упорядочена ещё одна пара: [1, 3, 3, 4, 2, 5, 7, 9]
Цикл № 24 Сравниваются: 4 2
Упорядочена ещё одна пара: [1, 3, 3, 2, 4, 5, 7, 9]
Цикл № 25 Сравниваются: 4 5
Цикл № 26 Сравниваются: 5 7
Цикл № 27 Сравниваются: 7 9
Цикл № 28 Сравниваются: 1 3
Цикл № 29 Сравниваются: 3 3
Цикл № 30 Сравниваются: 3 2
Упорядочена ещё одна пара: [1, 3, 2, 3, 4, 5, 7, 9]
Цикл № 31 Сравниваются: 3 4
Цикл № 32 Сравниваются: 4 5
Цикл № 33 Сравниваются: 5 7
Цикл № 34 Сравниваются: 7 9
Цикл № 35 Сравниваются: 1 3
Цикл № 36 Сравниваются: 3 2
Упорядочена ещё одна пара: [1, 2, 3, 3, 4, 5, 7, 9]
Цикл № 37 Сравниваются: 3 3
Цикл № 38 Сравниваются: 3 4
Цикл № 39 Сравниваются: 4 5
Цикл № 40 Сравниваются: 5 7
Цикл № 41 Сравниваются: 7 9
Цикл № 42 Сравниваются: 1 2
Цикл № 43 Сравниваются: 2 3
Цикл № 44 Сравниваются: 3 3
Цикл № 45 Сравниваются: 3 4
Цикл № 46 Сравниваются: 4 5
Цикл № 47 Сравниваются: 5 7
Цикл № 48 Сравниваются: 7 9
Отсортированный массив: [1, 2, 3, 3, 4, 5, 7, 9]Листинг 3. Процесс сортировки методом «пузырька».
4. Метод сортировки — «Сортировка перемешиванием».
def mySort(array):
left = 1
right = len(array)
while left<right:
for i in range(left, right):
if array[i] < array[i-1]:
array[i], array[i-1] = array[i-1], array[i]
if array[right-i] < array[right-i-1]:
array[right-i], array[right-i-1] = array[right-i-1], array[right-i]
left += 1; right -= 1
return array
a = [7, 5, 3, 1, 4, 9, 3, 2]
print(mySort(a))Программа 4, реализующая сортировку «перемешиванием».
Результат:
[1, 2, 3, 3, 4, 5, 7, 9]Сортировка перемешиванием, или Шейкерная сортировка, или двунаправленная (англ. Cocktail sort) —разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства. Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, её можно исключить из рассмотрения. Во-вторых, при движении от конца массива к началу минимальный элемент «всплывает» на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (то есть части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.
Алгоритм сортирует элементы непосредственно в исходном списке, поэтому он не требователен к ресурсам памяти.
Производительность алгоритма O(N2)
Листинг 4. Процесс сортировки методом «Сортировка перемешиванием».
5. Метод сортировки — «Сортировка слиянием».
Автор метода Джон фон Нейман.
def mySort(A):
if len(A) <=1:
return(A)
L = mySort(A[:len(A)//2])
R = mySort(A[len(A)//2:])
B = []
l=r=0
while l<len(L) and r<len(R):
B.append(L[l] if L[l] <= R[r] else R[r])
[l, r] = [l+1, r] if L[l] <= R[r] else [l, r+1]
for l in range(l, len(L)):
B.append(L[l])
for r in range(r, len(R)):
B.append(R[r])
return B
a = [7, 5, 3, 1, 4, 9, 3, 2]
print(mySort(a))Программа 5, реализующая сортировку «слиянием».
Результат:
[1, 2, 3, 3, 4, 5, 7, 9]Сортировку слиянием (merge sort) можно выполнить в следующем порядке:
Сортируемый массив разбивается на две части примерно одинакового размера.
Каждая из получившихся частей сортируется отдельно, например, рекурсивно, тем же алгоритмом.
Практически, рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
Два упорядоченных массива половинного размера соединяются в один поэлементно.
На каждом шаге мы берём меньший из двух первых элементов этих массивов и записываем его в результирующий массив. Счётчики номеров элементов результирующего массива и массива, из которого был взят элемент, увеличиваем на 1.
Когда один из исходных массивов закончился, мы добавляем все оставшиеся элементы второго массива в результирующий.
Для сортировки слиянием требуется O(N) дополнительной памяти.
Производительность алгоритма O(N log N)
Листинг 5. Процесс сортировки методом «Сортировка слиянием».
6. Метод сортировки — «Гномья сортировка».
def mySort(A):
i = 1
while i < len(A):
if A[i]<A[i-1]:
A[i], A[i-1] = A[i-1], A[i]
i = i-1 if i > 1 else i+1
else:
i += 1
return A
a = [7, 5, 3, 1, 4, 9, 3, 2]
print(mySort(a))Программа 6, реализующая «Гномью сортировку»
Результат:
[1, 2, 3, 3, 4, 5, 7, 9]«Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на текущий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.»
Дик Грун.
Алгоритм сортирует элементы непосредственно в исходном списке, поэтому он не требователен к ресурсам памяти.
Производительность алгоритма O(N2).
[7, 5, 3, 1, 4, 9, 3, 2]
i= 2 ; array= [5, 7, 3, 1, 4, 9, 3, 2]
i= 1 ; array= [5, 3, 7, 1, 4, 9, 3, 2]
i= 2 ; array= [3, 5, 7, 1, 4, 9, 3, 2]
i= 3 ; array= [3, 5, 7, 1, 4, 9, 3, 2]
i= 2 ; array= [3, 5, 1, 7, 4, 9, 3, 2]
i= 1 ; array= [3, 1, 5, 7, 4, 9, 3, 2]
i= 2 ; array= [1, 3, 5, 7, 4, 9, 3, 2]
i= 3 ; array= [1, 3, 5, 7, 4, 9, 3, 2]
i= 4 ; array= [1, 3, 5, 7, 4, 9, 3, 2]
i= 3 ; array= [1, 3, 5, 4, 7, 9, 3, 2]
i= 2 ; array= [1, 3, 4, 5, 7, 9, 3, 2]
i= 3 ; array= [1, 3, 4, 5, 7, 9, 3, 2]
i= 4 ; array= [1, 3, 4, 5, 7, 9, 3, 2]
i= 5 ; array= [1, 3, 4, 5, 7, 9, 3, 2]
i= 6 ; array= [1, 3, 4, 5, 7, 9, 3, 2]
i= 5 ; array= [1, 3, 4, 5, 7, 3, 9, 2]
i= 4 ; array= [1, 3, 4, 5, 3, 7, 9, 2]
i= 3 ; array= [1, 3, 4, 3, 5, 7, 9, 2]
i= 2 ; array= [1, 3, 3, 4, 5, 7, 9, 2]
i= 3 ; array= [1, 3, 3, 4, 5, 7, 9, 2]
i= 4 ; array= [1, 3, 3, 4, 5, 7, 9, 2]
i= 5 ; array= [1, 3, 3, 4, 5, 7, 9, 2]
i= 6 ; array= [1, 3, 3, 4, 5, 7, 9, 2]
i= 7 ; array= [1, 3, 3, 4, 5, 7, 9, 2]
i= 6 ; array= [1, 3, 3, 4, 5, 7, 2, 9]
i= 5 ; array= [1, 3, 3, 4, 5, 2, 7, 9]
i= 4 ; array= [1, 3, 3, 4, 2, 5, 7, 9]
i= 3 ; array= [1, 3, 3, 2, 4, 5, 7, 9]
i= 2 ; array= [1, 3, 2, 3, 4, 5, 7, 9]
i= 1 ; array= [1, 2, 3, 3, 4, 5, 7, 9]
i= 2 ; array= [1, 2, 3, 3, 4, 5, 7, 9]
i= 3 ; array= [1, 2, 3, 3, 4, 5, 7, 9]
i= 4 ; array= [1, 2, 3, 3, 4, 5, 7, 9]
i= 5 ; array= [1, 2, 3, 3, 4, 5, 7, 9]
i= 6 ; array= [1, 2, 3, 3, 4, 5, 7, 9]
i= 7 ; array= [1, 2, 3, 3, 4, 5, 7, 9]
i= 8 ; array= [1, 2, 3, 3, 4, 5, 7, 9]
[1, 2, 3, 3, 4, 5, 7, 9]Листинг 6. Процесс сортировки методом «Гномья сортировка».
7. Метод сортировки «Сортировка расчёской»
def mySort(A):
step = len(A) - 1
while step > 0:
for i in range(0, len(A)-step):
if (A[i] > A[i+step]):
A[i], A[i+step] = A[i+step], A[i]
step = int(step//1.25)
return A
a = [7, 5, 3, 1, 4, 9, 3, 2]
print(mySort(a))Программа 7, реализующая сортировку «расчёской».
Результат:
[1, 2, 3, 3, 4, 5, 7, 9]Сортировка расчёской (comb sort) выполняется исходя из предположения, что при использовании большего шага между сравниваемыми элементами, чем при сортировке пузырьком, упорядочивание происходит быстрее.
Изначально сравнивается первый и последний элемент массива, шаг на единицу меньше размера массива.
На каждой итерации шаг уменьшается на фактор уменьшения (делится нацело на 1,247). Итерации продолжаются до тех пор, пока шаг не станет равным 1. Затем массив сортируется сортировкой пузырьком, причём, за один проход.
Производительность алгоритма O()
Автор метода Влодзимеж Добосевич в 1980 г. и переоткрыватели Стивен Лэйси и Ричард Бокса в 1991 г.
[7, 5, 3, 1, 4, 9, 3, 2]
Шаг 7 : 7 > 2
[2, 5, 3, 1, 4, 9, 3, 7]
Шаг 5 : 2 > 9
Шаг 5 : 5 > 3
[2, 3, 3, 1, 4, 9, 5, 7]
Шаг 5 : 3 > 7
Шаг 4 : 2 > 4
Шаг 4 : 3 > 9
Шаг 4 : 3 > 5
Шаг 4 : 1 > 7
Шаг 3 : 2 > 1
[1, 3, 3, 2, 4, 9, 5, 7]
Шаг 3 : 3 > 4
Шаг 3 : 3 > 9
Шаг 3 : 2 > 5
Шаг 3 : 4 > 7
Шаг 2 : 1 > 3
Шаг 2 : 3 > 2
[1, 2, 3, 3, 4, 9, 5, 7]
Шаг 2 : 3 > 4
Шаг 2 : 3 > 9
Шаг 2 : 4 > 5
Шаг 2 : 9 > 7
[1, 2, 3, 3, 4, 7, 5, 9]
Шаг 1 : 1 > 2
Шаг 1 : 2 > 3
Шаг 1 : 3 > 3
Шаг 1 : 3 > 4
Шаг 1 : 4 > 7
Шаг 1 : 7 > 5
[1, 2, 3, 3, 4, 5, 7, 9]
Шаг 1 : 7 > 9Листинг 7. Процесс сортировки методом «сортировка расчёской».
8. Метод сортировки «Bogosort»
from random import shuffle
def mySort(array):
while True:
for i in range(0, len(array)-1):
if (array[i] > array[i+1]):
shuffle(array)
break
if i == len(array)-2: return
a = [7, 5, 3, 1, 4, 9, 3, 2]
mySort(a)
print(a)Программа 8, реализующая сортировку «Bogosort».
Результат:
[1, 2, 3, 3, 4, 5, 7, 9]Сортировка Bogosort выполняется исходя из предположения, что при перемешивании списка, случайным образом список может оказаться отсортированным. В процессе сортировки методом Bogosort сначала проверяют не стоят ли его элементы в правильном порядке, например, каждый следующий элемент должен быть не меньше предыдущего. Если список оказался не отсортирован, его элементы перемешивают и опять переходят к проверке.
Производительность алгоритма крайне низкая.
========== RESTART: ~/Алгоритмы/Sort/Bogosort01.py ==========
2178 [1, 2, 3, 3, 4, 5, 7, 9]
>>>
========== RESTART: ~/Алгоритмы/Sort/Bogosort01.py ==========
34898 [1, 2, 3, 3, 4, 5, 7, 9]
>>>
========== RESTART: ~/Алгоритмы/Sort/Bogosort01.py ==========
5342 [1, 2, 3, 3, 4, 5, 7, 9]
>>>
========== RESTART: ~/Алгоритмы/Sort/Bogosort01.py ==========
1432 [1, 2, 3, 3, 4, 5, 7, 9]
>>>
========== RESTART: ~/Алгоритмы/Sort/Bogosort01.py ==========
17474 [1, 2, 3, 3, 4, 5, 7, 9]
>>>
========== RESTART: ~/Алгоритмы/Sort/Bogosort01.py ==========
3296 [1, 2, 3, 3, 4, 5, 7, 9]
>>>
========== RESTART: ~/Алгоритмы/Sort/Bogosort01.py ==========
39032 [1, 2, 3, 3, 4, 5, 7, 9]
>>>
========== RESTART: ~/Алгоритмы/Sort/Bogosort01.py ==========
69902 [1, 2, 3, 3, 4, 5, 7, 9]Листинг 8. Процесс сортировки методом «Bogosort».
Прочие методы сортировки
Сортировка с помощью двоичного дерева.
Timsort.
Сортировка Шелла.
Плавная сортировка.
Быстрая сортировка.
Пирамидальная сортировка.
Интроспективная сортировка.
Терпеливая сортировка.
Блочная сортировка.
Поразрядная сортировка.
Сортировка подсчётом.
Топологическая сортировка.
Приложения:
Программы с помощью которых получены листинги процессов сортировки:
def mySort(array):
for i in range(1, len(array)):
print ("Порядковый номер элемента в списке i =", i)
print ("Значение array[i] =", array[i])
print(" ")
while (i > 0 and array[i] < array[i-1]):
array[i], array[i-1] = array[i-1], array[i]
i -= 1
print(" ", array)
print(" ")
return array
a = [7, 5, 3, 1, 4, 9, 3, 2]
print("Список до сортировки:", a)
print(" ")
print("Список после сортировки:", mySort(a))Программа к листингу 1.
def mySort(array):
k = 0
for i in range(0, len(array)):
print("Список отсортирован до элемента:",i, array)
for n in range(i+1, len(array)):
print("Цикл №"," "if k<10 else "",k, " Сравниваем: "," "*i, array[i]," "*(n-i-1),array[n])
k += 1
if (array[n] < array[i]):
array[n], array[i] = array[i], array[n]
return array
a = [7, 5, 3, 1, 4, 9, 3, 2]
print(mySort(a))Программа к листингу 2.
def mySort(array):
noSorted = True
n = 0
while noSorted:
noSorted = False
for i in range(0, len(array)-1):
print("Цикл №"," "if n<10 else "", n," Сравниваются: ", " "*i, array[i],'',array[i+1])
n += 1
if (array[i] > array[i+1]):
noSorted = True
array[i], array[i+1] = array[i+1], array[i]
print("Упорядочена ещё одна пара: ", array)
return array
a = [7, 5, 3, 1, 4, 9, 3, 2]
print("Не отсортированный массив: ",a)
print(" Отсортированный массив: ",mySort(a))
Программа к листингу 3.
def mySort(A):
step = len(A) - 1
while step > 0:
for i in range(0, len(A)-step):
print('Шаг', step, ':', A[i], '>', A[i+step])
if (A[i] > A[i+step]):
A[i], A[i+step] = A[i+step], A[i]
print(" ",A)
step = int(step//1.25)
return A
a = [7, 5, 3, 1, 4, 9, 3, 2]
print(" ",a)
mySort(a)Программа к листингу 7.
from random import shuffle
def mySort(array):
n = 0
while True:
for i in range(0, len(array)-1):
if (array[i] > array[i+1]):
shuffle(array)
n += 1
break
if i == len(array)-2: return n
a = [7, 5, 3, 1, 4, 9, 3, 2]
n = mySort(a)
print(n, a)Программа к листингу 8.
Авторы:
визуализация процессов: Лутченков Аркадий Витальевич
алгоритмы: Диордица Александр Александрович
Литература :
Стивенс Род. Алгоритмы. Теория и практическое применение.
Дональд Э. Кнут. Искусство программирования. Том 3. Сортировка и поиск.
