Бързо сортиране

Бързо сортиране (на английски: quick sort) е добре известен сортиращ алгоритъм, разработен от Ч. А. Р. Хор през 1960 г. и публикуван през 1961 г.,. Основната част на алгоритъма се състои в сравняващо сортиране.

В най-лошия случай алгоритъмът има сложност O(n2). Средната времева сложност е O(n log n), а амортизираната сложност е 1,386 n log n сравнения. В практиката бързото сортиране е с по-добро време от други сортиращи алгоритми с време O(n log n). Освен това, последователността на бързото сортиране и локализираните препратки към паметта работят добре с кеша. Бързото сортиране се основава на сравнения. То не е устойчиво, тоест може да размества елементи с еднакви ключове. Класическият алгоритъм използва допълнителен масив, но съществува вариант, който сортира данните на място – без заделяне на втори масив, така че се използва само O(log n) допълнителна памет.

Нагледно бързо сортиране на списък с числа. Главният елемент е в червено.

Принцип на действие
1. Избира се „главен“ елемент от списъка с елементи, които ще бъдат сортирани.
2. Списъкът се пренарежда така, че всички елементи, които са по-малки от „главния“ се поставят вляво от него, а всички, които са по-големи – вдясно от него.
3. Рекурсивно се повтарят горните стъпки върху списъка с по-малките и списъка с по-големите елементи.
4. Получените списъци се сливат (конкатенация) и се получава сортираният списък.

 function quicksort('array')
      if length('array') ≤ 1
          return 'array'  // масив от нула или един елементи е вече сортиран
      select and remove a pivot element 'pivot' from 'array'  // вижте избор на "главен" елемент по-долу
      create empty lists 'less' and 'greater'
      for each 'x' in 'array'
          if 'x' ≤ 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
      return concatenate(quicksort('less'), list('pivot'), quicksort('greater')) // две рекурсивни извиквания

Оптимизация
Съществуват още две важни оптимизации, за които обикновено се счита, че също са предложени от Р. Седжуик, и са широко използвани в практиката:

За да е сигурно, че се използва най-много O(log N) място, първо използваме рекурсия в по-малката част на масива, а за другата използваме опашкова рекурсия (tail call).
С оглед на алгоритъма за сортиране чрез вмъкване, който има по-малък константен фактор и по тази причина е по-ефективен при къси масиви, чиито дължини са по-малки от граничната стойност k, която се определя експериментално. На практика това може да се реализира чрез спиране на рекурсията, когато остават по-малко от k елемента, тоест всеки елемент ще бъда на най-много k позиции от крайното си местоположение. След това едно изпълнение на сортиране чрез вмъкване завършва подреждането за O(k×n) време. Отделното сортиране чрез вмъкване на всеки малък сегмент увеличава времето за обработка чрез стартиране и спиране на много малки сортирания, но спестява усилията за сортиране на ключовете в краищата на сегмента, тъй като ключовете ще са подредени заради начина, по който работи бързото сортиране.