Quick Sort

Adam Boduch

Złożoność czasowa:

  • średnia: O(n log n)
  • pesymistyczna: O(n^2)
    Pamięciowa:
  • wersja z zamianą elementów w tablicy - średnio: O(log n)
  • wersja z tworzeniem nowych tablic: O(n)

Metoda polega na wybraniu jednego elementu spośród tablicy i przeniesieniu wszystkich elementów o wyższym kluczu na prawo od tego elementów i analogicznie elementów o kluczu mniejszym na lewo. Następnie funkcja sortująca zostaje wywołana po raz kolejny na obu częściach tablicy.

Algorytm szybkiego sortowania średnio jest jednym z najszybszych metod porządkowania elementów. Jego czas (złożoność) zależy jednak do doborze odpowiedniego elementu dzielącego, do uzyskania najlepszego efektu ten element powinien być medianą całego ciągu, jednak ze względu na to, że policzenie samej mediany trwa stosunkowo długo często wybiera się element środkowy (z dokładnością do liczby naturalnej), niektóre implementacje wykorzystują też element losowany lub medianę 3 losowo wybranych liczb.

Pseudokod

  1. jeżeli rozmiar podanej tablicy jest <= 1 to zwróć tą tablicę
  2. wyznacz element dzielący
  3. podziel tablice na 2 części: jedną z elementami mniejszymi od elementu dzielącego, drugą z większymi
  4. posortuj część z mniejszymi elementami rekursywnie wywołując quicksort
  5. posortuj część z większymi elementami rekursywnie wywołując quicksort
  6. zwróć tablicę: mniejsze+element dzielący+większe

Implementacja(Delphi)

procedure Sort(var iArray: array of Integer);

  procedure QuickSort(iLow, iHigh : Integer {Skrajne elementy wyznaczające sortowany zakres w tablicy});
  var
    iLo, iHi : Integer;
    x, Temp : Integer;
  begin
    {Podstawmy zakresy pod nasze zmienne pomocnicze}
    iLo := iLow;
    iHi := iHigh;
    {Wyznaczmy element według którego sortujemy. Można przyjąć dowolny, jednak zwykle bierze się środek zakresu, gdyż przy częściowo posortowanej liście zwykle element ten wyznacza środek zakresu (tyle samo elementów większych jak i mniejszych)}
    X := iArray[(iLow + iHigh) div 2];
    repeat
      {przeszukując tablicę od lewej wyszukajmy pierwszy element większy od naszego elementu podziału X}
      while iArray[iLo] < X do Inc(iLo);
      {przeszukując tablicę od prawej wyszukajmy pierwszy element mniejszy od naszego elementu podziału X}
      while iArray[iHi] > X do Dec(iHi);
      {Jeżeli indeks pierwszego wyszukanego elementu jest mniejszy od drugiego...}
      if (iLo <= iHi) then
      {To zamieńmy elementy miejscami}
      begin
        Temp := iArray[iLo];
        iArray[iLo] := iArray[iHi];
        iArray[iHi] := Temp;
        {Przeskoczmy do następnych elementów}
        Inc(iLo);
        Dec(iHi);
      end;
    {I powtarzajmy to do momentu, aż zrównają się indeksy elementów wyszukiwanych z prawej i z lewej (dokładniej to jak przeszkodzą, abyśmy nie utknęli w miejscu}
    until iLo > iHi;
    {Jeżeli są jeszcze jakieś elementy do posortowania w lewej części przedziału to posortujmy je}
    if (iHi > iLow) then QuickSort(iLow, iHi);
    {Tak samo, jeżeli są z prawej}
    if (iLo < iHigh) then QuickSort(iLo, iHigh);
  end;

begin
  QuickSort(Low(iArray), High(iArray));
end;

Implementacja (Python)

def quicksort(a):
    if len(a) <= 1:
        return a
    m = a[len(a)/2] # wyznaczenie elementu rozdzielajacego
    return quicksort([i for i in a if i <= m]) + \     # posortowanie elementow mniejszych
        quicksort([i for i in a if i > m])             # posortowanie elementow wiekszych

Implementacje (C/C++)

#include <stdlib.h>

void
qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

11 komentarzy

Python ma Quick Sort wbudowany (metoda sort):

a = [1, 4, 6,9,4, 2, 4.5, -100]
a.sort()
a
[-100, 1, 2, 4, 4, 4.5, 6, 9]

Funkcja sort w STL jest różnie implementowana w zależności od biblioteki której używasz.

Np. w SGI używany jest introsort - trochę zmodyfikowana wersja quicksort-a.

Warto wspomnieć też, że STL z C++ w nagłówku <algorithm> posiada zaimplementowanego Quick Sorta (funkcja sort)

Aby sortować tablicę stringów należy w procedurze zmienć typ tablicy na String, powinna więc mieć następującą postać: procedure Sort(var iArray: array of String); oraz zmienić typ zmiennych X i Temp , w podprocedurze QuickSort, z Integer na String. I to wszystko.

egh,a jakby ktos chcial to prosze to samo ale w cpp

void qsort (int *tab, int left, int right)
{
if (left < right)
 {
  int m=left;
  for (int i=left+1;i<right;i++)
      if (tab[i]<tab[left])
          zamiana (tab[++m],tab[i]);
  zamiana (tab[left],tab[m]);
  qsort (tab,left,m);
  qsort (tab,m+1,right);
  }
}

sama procedurka nalezy mu podac zakres elemnutf tablicy left i right

Niezly algorytm wporownaniu do HeapSort ten jest o niebo lepszy

a jak posortować tablice stringów?

Mam nadzieję, że komentarze zamiast pseudokodu wystarczą.

Zgadzam się z Waldim w 100%. Ponadto, czy nie lepiej rozpisać to w pseudokodzie (tak jak np. w książce "Perełki oprogramowania", str. 151). Nie wszyscy są maniakami Delphi (Kapustki w szczególności nie są). :-)

Troche za mało komentazry można się pogubić w kodzie