Бързо сортиране
From Wikipedia, the free encyclopedia
Бързо сортиране (на английски: quick sort) е добре известен сортиращ алгоритъм, разработен от Ч. А. Р. Хор през 1960 г.[1] и публикуван през 1961 г.,[2]. Основната част на алгоритъма се състои в сравняващо сортиране.
В най-лошия случай алгоритъмът има сложност O(n2). Средната времева сложност е O(n log n), а амортизираната сложност е 1,386 n log n сравнения. В практиката бързото сортиране е с по-добро време от други сортиращи алгоритми с време O(n log n). Освен това, последователността на бързото сортиране и локализираните препратки към паметта работят добре с кеша. Бързото сортиране се основава на сравнения. То не е устойчиво, тоест може да размества елементи с еднакви ключове. Класическият алгоритъм използва допълнителен масив, но съществува вариант, който сортира данните на място – без заделяне на втори масив, така че се използва само O(log n) допълнителна памет.