Визуализация быстрой сортировки

Что такое алгоритм быстрой сортировки?

Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем {\displaystyle O(n\log n)}O(n\log n) обменов при упорядочении {\displaystyle n}n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Общее описание

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного в том числе своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы (таким образом улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов).

Общая идея алгоритма состоит в следующем:

Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность (см. ниже).

• Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие».
• Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
• На практике массив обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения (см. ниже).

Хоар разработал этот метод применительно к машинному переводу; словарь хранился на магнитной ленте, и сортировка слов обрабатываемого текста позволяла получить их переводы за один прогон ленты, без перемотки её назад. Алгоритм был придуман Хоаром во время его пребывания в Советском Союзе, где он обучался в Московском университете компьютерному переводу и занимался разработкой русско-английского разговорника.

Реализации

JavaScript

  function quickSort(arr, left, right) {
    var i = left;
    var j = right;
    var tmp;
    var pivotidx = (left + right) / 2;
    var pivot = parseInt(arr[pivotidx.toFixed()]);
    /* partition */
    while (i <= j)
    {
      while (parseInt(arr[i]) < pivot)
        i++;
      while (parseInt(arr[j]) > pivot)
        j--;
      if (i <= j)
      {
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
        i++;
        j--;
      }
    }

    /* recursion */
    if (left < j)
      this.quickSort(arr, left, j);
    if (i < right)
      this.quickSort(arr, i, right);

    return arr;
  }

Go / Golang

  func quicksort(arr []int) []int {
    if len(arr) <= 1 {
      return arr
    } else {
      pivot := arr[0]
      smaller := make([]int, 0)
      greater := make([]int, 0)
      for _, num := range arr[1:] {
        if num <= pivot {
          smaller = append(smaller, num)
        } else {
          greater = append(greater, num)
        }
      }
      smaller = quicksort(smaller)
      greater = quicksort(greater)
      return append(append(smaller, pivot), greater...)
    }
  }

Python

 def partition(array, low, high):
  pivot = array[high]

  i = low - 1

  for j in range(low, high):
    if array[j] <= pivot:
      i = i + 1
      (array[i], array[j]) = (array[j], array[i])

  (array[i + 1], array[high]) = (array[high], array[i + 1])

  return i + 1

def quickSort(array, low, high):
  if low < high:

    pi = partition(array, low, high)

    quickSort(array, low, pi - 1)

    quickSort(array, pi + 1, high)


data = [8, 7, 2, 1, 0, 9, 6] print("Unsorted Array") print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order:') print(data) 

Source: Wikipedia