Проходим последовательно по всем элементам списка и попарно сравниваем их между собой, если выбранный порядок в паре нарушен, то мы меняем элементы местами. Таким образом за один проход один элемент занимает свое место, всплывает, как пузырек. А за N - 1 (где N - кол-во элементов списка) проходов мы точно отсортируем весь список.
def bubbleSort(source):
work_list = source[:]
for passnum in range(len(work_list) - 1, 0, -1):
for i in range(passnum):
if work_list[i] > work_list[i + 1]:
(work_list[i + 1], work_list[i]) = (work_list[i], work_list[i + 1])
return work_list
Т.к. в ситуации когда сравнив все значения в списке нам не прешлось переставлять (менять местами) элементы - это значит, что список уже отсортирован. Используя этот факт мы можем сократить время работы алгоритма.
def shortBubbleSort(source):
work_list = source[:]
exchanges = True
passnum = len(work_list) - 1
while passnum > 0 and exchanges:
exchanges = False
for i in range(passnum):
if work_list[i] > work_list[i + 1]:
exchanges = True
(work_list[i + 1], work_list[i]) = (work_list[i], work_list[i + 1])
passnum = passnum - 1
return work_list
def selectionSort(work_list):
for fillslot in range(len(work_list) - 1, 0, -1):
positionOfMax = 0
for location in range(1, fillslot + 1):
if work_list[location] > work_list[positionOfMax]:
positionOfMax = location
(work_list[fillslot], work_list[positionOfMax]) = (work_list[positionOfMax], work_list[fillslot] )
Сортировка слияниями — устойчивый алгоритм сортировки, использующий O(n) дополнительной памяти и работающий за O(nlog(n)). Исходный массив разбивается пополам на два и для каждой части решается задача сортировки, а затем две части сливаются в одну. Сортировка частей происходит также разбиванием пополам и так до тех пор пока часть не окажется состоящей из одного элемента, который по определению является отсортированным. Примерно по шагам алгоритм можно описать как:
Основное значение в этом алгоритме играет функция слияния двух отсортированных массивов. Рассмотрим ее. Мы последовательно сравниваем элементы массивов, начиная с начала, и наименьший записываем в результирующий массив, а в том массиве откуда был взят элемент берем для сравнения следующий элемент и так выполняем данные действия пока один массив не окажется пуст, тогда оставшиеся элементы, из второго массива, мы просто дописываем "как есть" в результирующий.
# -*- coding: utf-8 -*-
# file: merge.py
def merge(arr_a, arr_b):
'''
Слияние двух неубывающих массивов
>>> merge([1,2,3],[4,5,6])
[1, 2, 3, 4, 5, 6]
>>> merge([4,5,6],[1,2,3])
[1, 2, 3, 4, 5, 6]
'''
arr_c = []
i, j = 0, 0
while i < len(arr_a) and j < len(arr_b):
if arr_a[i] <= arr_b[j]:
arr_c.append(arr_a[i])
i += 1
else:
arr_c.append(arr_b[j])
j += 1
if arr_a[i:]: arr_c += arr_a[i:]
if arr_b[j:]: arr_c += arr_b[j:]
return arr_c
if __name__ == "__main__":
import doctest
doctest.testmod(verbose=True)
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, К. Штайн. Алгоритмы: построение и анализ, 3-е издание = Introduction to Algorithms, Third Edition. — М.: «Вильямс», 2013. — 1328 с. — ISBN 978-5-8459-1794-2. Стр. 52
Различные визулизаторы алгоритмов сортировки: