Алгоритмы сортировки

Сортировка пузырьком. The Bubble Sort.

Проходим последовательно по всем элементам списка и попарно сравниваем их между собой, если выбранный порядок в паре нарушен, то мы меняем элементы местами. Таким образом за один проход один элемент занимает свое место, всплывает, как пузырек. А за 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
                          
          

Т.к. в ситуации когда сравнив все значения в списке нам не прешлось переставлять (менять местами) элементы - это значит, что список уже отсортирован. Используя этот факт мы можем сократить время работы алгоритма.

Сокращенная сортировка пузырьком. The short bubble sort.

          
          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
                  
          

Сортировка прямым выбором. The Selection Sort.

          
          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] ) 
          
          

Сортировка вставкой. The Insertion Sort.

Сортировка вставкой — устойчивый алгоритм сортировки, использующий O(1) дополнительной памяти и работающий за O(n^2).
          

Пирамидальная сортировка

          

Быстрая сортировка

          

Сортировка слияниями. The Merge Sort.

Сортировка слияниями — устойчивый алгоритм сортировки, использующий O(n) дополнительной памяти и работающий за O(nlog(n)). Исходный массив разбивается пополам на два и для каждой части решается задача сортировки, а затем две части сливаются в одну. Сортировка частей происходит также разбиванием пополам и так до тех пор пока часть не окажется состоящей из одного элемента, который по определению является отсортированным. Примерно по шагам алгоритм можно описать как:

  1. Если в рассматриваемом массиве один элемент, то он уже отсортирован — алгоритм завершает работу.
  2. Иначе массив разбивается на две части, которые сортируются рекурсивно.
  3. После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.

Основное значение в этом алгоритме играет функция слияния двух отсортированных массивов. Рассмотрим ее. Мы последовательно сравниваем элементы массивов, начиная с начала, и наименьший записываем в результирующий массив, а в том массиве откуда был взят элемент берем для сравнения следующий элемент и так выполняем данные действия пока один массив не окажется пуст, тогда оставшиеся элементы, из второго массива, мы просто дописываем "как есть" в результирующий.

          
          # -*- 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

Сортировка подсчетом

          

Поразрядная сортировка

          

Различные визулизаторы алгоритмов сортировки: