Spisu treści:
Definicja - Co oznacza Quicksort?
Quicksort to popularny algorytm sortowania, który jest często szybszy w praktyce w porównaniu do innych algorytmów sortowania. Wykorzystuje strategię „dziel i rządź”, aby szybko sortować elementy danych, dzieląc dużą tablicę na dwie mniejsze tablice. Został opracowany przez Charlesa Antony'ego Richarda Hoare'a (powszechnie znany jako CAR Hoare lub Tony Hoare) w 1960 r. Dla projektu tłumaczenia maszynowego dla National Physical Laboratory.Techopedia wyjaśnia Quicksort
Quicksort to algorytm używany do szybkiego sortowania elementów w tablicy bez względu na to, jak duża jest tablica. Jest dość skalowalny i działa stosunkowo dobrze w przypadku małych i dużych zestawów danych oraz jest łatwy do wdrożenia przy niewielkiej złożoności czasu. Robi to za pomocą metody „dziel i rządź”, która dzieli pojedynczą dużą tablicę na dwie mniejsze, a następnie powtarza ten proces dla wszystkich utworzonych tablic, aż sortowanie się zakończy.
Algorytm Quicksort wykonuje się w następujący sposób:
- Punkt obrotu jest wybierany z tablicy.
- Zmieniono kolejność tablic, tak aby wszystkie wartości mniejsze niż oś przestawna były przenoszone przed nią, a wszystkie wartości większe niż oś przestawiana były przenoszone za nią, z wartościami równymi osi przestawianej w obie strony. Po wykonaniu tej czynności oś obrotu znajduje się w końcowej pozycji.
- Powyższy krok powtarza się dla każdej podtablicy o mniejszych wartościach, a także wykonuje się osobno dla podtablicy o większych wartościach.
Powtarzane jest to do momentu posortowania całej tablicy.
