Algorytmy sortowania danych

Wiadomości wstępne

Sortowanie to proces ustawiania zbioru obiektów w określonym porządku, stosowany w celu ułatwienia późniejszego wyszukiwania elementów. Rozróżniamy metody wewnętrzne (tablice w pamięci operacyjnej) i zewnętrzne (pliki). Metody proste wymagają rzędu n² porównań, dobre algorytmy — n·log₂(n). Miarami efektywności są: liczba porównań kluczy Po i liczba przesunięć Pr.

1. Sortowanie przez proste wstawianie

Metoda stosowana powszechnie przez grających w karty. Ciąg dzielimy na wynikowy i źródłowy — w każdym kroku i-ty element źródłowego wstawiamy we właściwe miejsce wynikowego.

procedure ProsteWstawianie;
var i,j : Indeks; x : Obiekt;
begin
  for i := 2 to n do
  begin
    x    := a[i];     { element do wstawienia }
    a[0] := x;        { wartownik }
    j    := i - 1;
    while x.Klucz < a[j].Klucz do
    begin
      a[j+1] := a[j]; { przesunięcie o jeden w prawo }
      j := j - 1
    end;
    a[j+1] := x       { wstawienie na właściwe miejsce }
  end
end;

Przykład: 44 55 12 42 94 18 06 67 → 06 12 18 42 44 55 67 94

2. Wstawianie połówkowe (bisekcja)

Usprawnienie prostego wstawiania — miejsce wstawienia szukamy metodą bisekcji. Zmniejsza liczbę porównań, ale nie liczbę przesunięć, więc zysk jest marginalny w praktyce.

procedure WstawianiePolowkowe;
var i,j,l,p,m : Indeks; x : Obiekt;
begin
  for i := 2 to n do
  begin
    x := a[i]; l := 1; p := i - 1;
    while l <= p do
    begin
      m := (l + p) div 2;
      if x.Klucz < a[m].Klucz then p := m - 1
      else l := m + 1
    end;
    for j := i - 1 downto l do
      a[j+1] := a[j];
    a[l] := x
  end
end;

3. Sortowanie przez proste wybieranie

W każdym kroku wybieramy obiekt o najmniejszym kluczu i wymieniamy go z pierwszym. Przeważnie lepsze od prostego wstawiania, choć przy częściowo posortowanych danych wstawianie może być szybsze.

procedure ProsteWybieranie;
var i,j,k : Indeks; x : Obiekt;
begin
  for i := 1 to n-1 do
  begin
    k := i; x := a[i];
    for j := i+1 to n do
      if a[j].Klucz < x.Klucz then
      begin k := j; x := a[j] end;
    a[k] := a[i]; a[i] := x  { zamiana }
  end
end;

4. Sortowanie bąbelkowe

Powtarzamy przejście przez tablicę, przesuwając za każdym razem najmniejszy element na lewy koniec. Jak bąbelki w wodzie — lekkie idą w górę. Istnieje powiedzenie: absolutnie każdy program można poprawić...

procedure SortowanieBabelkowe;
var i,j : Indeks; x : Obiekt;
begin
  for i := 2 to n do
    for j := n downto i do
      if a[j-1].Klucz > a[j].Klucz then
      begin
        x := a[j-1]; a[j-1] := a[j]; a[j] := x
      end
end;

5. Sortowanie mieszane (Cocktail Sort)

Trzy ulepszenia bąbelkowego: zapamiętanie czy dokonano zmian, zapamiętanie pozycji ostatniej zamiany, zmiana kierunku przejść. Efekt? Marginalny, bo przesunięcia wciąż dominują nad porównaniami.

procedure SortowanieMieszane;
var j,k,l,p : Indeks; x : Obiekt;
begin
  l := 2; p := n; k := n;
  repeat
    for j := p downto l do    { przejscie "w gore" }
      if a[j-1].Klucz > a[j].Klucz then
      begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j end;
    l := k + 1;
    for j := l to p do           { przejscie "w dol" }
      if a[j-1].Klucz > a[j].Klucz then
      begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j end;
    p := k - 1
  until l > p
end;

6. Sortowanie Shella (Donald Shell, 1959)

Proste wstawianie ma jedną wadę: element, który powinien trafić na sam początek, wędruje tam po jednym miejscu. Shell zauważył, że jeśli najpierw poukładamy elementy odległe o h pozycji, a potem stopniowo zmniejszamy h aż do jedynki, to ostatni przebieg (zwykłe wstawianie) zastanie tablicę już prawie posortowaną — a wtedy jest bardzo szybki.

Cała sztuka tkwi w doborze ciągu odstępów. Najlepszy znany praktycznie jest ciąg Ciury: 1, 4, 10, 23, 57, 132, 301, 701, dalej mnożony przez ok. 2,25.

procedure SortowanieShella;
var i,j,h,k : Indeks; x : Obiekt;
begin
  for k := LiczbaOdstepow downto 1 do
  begin
    h := Odstep[k];              { 701, 301, 132, ... 4, 1 }
    for i := h+1 to n do
    begin
      x := a[i]; j := i;
      while (j > h) and (a[j-h].Klucz > x.Klucz) do
      begin
        a[j] := a[j-h]; j := j - h
      end;
      a[j] := x
    end
  end
end;

Kilka linijek więcej niż proste wstawianie, a przy 100 000 elementów jest od niego ponad 70 razy szybsze. Nie wymaga przy tym ani jednego bajtu dodatkowej pamięci — to wciąż najlepszy wybór, gdy pamięci brakuje.

7. Sortowanie przez scalanie (John von Neumann, 1945)

Dzielimy tablicę na pół, sortujemy rekurencyjnie każdą połowę, a potem scalamy dwie posortowane części w jedną — przebiegając je równolegle i biorąc za każdym razem mniejszy element. Scalanie dwóch uporządkowanych ciągów jest liniowe, a poziomów podziału jest log₂(n), stąd n·log(n).

procedure Scalaj(l, m, p : Indeks);
var i,j,k : Indeks;
begin
  i := l; j := m + 1; k := l;
  while (i <= m) and (j <= p) do
  begin
    if a[i].Klucz <= a[j].Klucz then
    begin b[k] := a[i]; i := i + 1 end
    else
    begin b[k] := a[j]; j := j + 1 end;
    k := k + 1
  end;
  while i <= m do begin b[k]:=a[i]; i:=i+1; k:=k+1 end;
  while j <= p do begin b[k]:=a[j]; j:=j+1; k:=k+1 end;
  for k := l to p do a[k] := b[k]
end;

procedure Scalanie(l, p : Indeks);
var m : Indeks;
begin
  if l < p then
  begin
    m := (l + p) div 2;
    Scalanie(l, m);
    Scalanie(m+1, p);
    Scalaj(l, m, p)
  end
end;

Ma dwie cechy, których Quicksort nie ma. Po pierwsze jest stabilny — elementy o równych kluczach zachowują swoją pierwotną kolejność, co ma znaczenie przy sortowaniu po wielu polach naraz. Po drugie n·log(n) jest gwarantowane w każdym przypadku, także pesymistycznym. Cenę płaci się pamięcią: potrzebna jest dodatkowa tablica b wielkości n.

To także jedyny z omawianych algorytmów, który naturalnie działa na plikach — nie trzeba mieć wszystkich danych w pamięci naraz, wystarczy czytać dwa strumienie i pisać trzeci.

8. Sortowanie kopcowe — heapsort (J.W.J. Williams, 1964)

Ulepszenie prostego wybierania. Tam szukanie najmniejszego elementu kosztowało n porównań; tutaj budujemy z tablicy kopiec — drzewo binarne, w którym rodzic jest zawsze większy od swoich dzieci. Znalezienie największego elementu to wtedy zajrzenie do korzenia, a naprawienie kopca po jego usunięciu kosztuje tylko log(n).

Piękno rozwiązania polega na tym, że drzewo trzymamy w tej samej tablicy: dziećmi elementu i są elementy 2i oraz 2i+1.

procedure Przesiej(i, n : Indeks);
var c : Indeks; x : Obiekt;
begin
  x := a[i];
  while 2*i <= n do
  begin
    c := 2*i;                    { lewe dziecko }
    if (c < n) and (a[c+1].Klucz > a[c].Klucz) then
      c := c + 1;                { prawe jest wieksze }
    if a[c].Klucz <= x.Klucz then Break;
    a[i] := a[c]; i := c
  end;
  a[i] := x
end;

procedure Kopcowe;
var i : Indeks; x : Obiekt;
begin
  for i := n div 2 downto 1 do   { budowa kopca }
    Przesiej(i, n);
  for i := n downto 2 do
  begin
    x := a[1]; a[1] := a[i]; a[i] := x;   { korzen na koniec }
    Przesiej(1, i-1)                      { napraw kopiec }
  end
end;

Heapsort nie ma przypadku pesymistycznego — zawsze n·log(n), i to bez dodatkowej pamięci. W praktyce bywa nieco wolniejszy od Quicksorta, bo skacze po tablicy w sposób nieprzyjazny dla pamięci podręcznej procesora. Właśnie dlatego służy dziś głównie jako zabezpieczenie: gdy Quicksort wpadnie w zbyt głęboką rekurencję, biblioteki przełączają się na heapsort.

9. Quicksort — sortowanie szybkie (C.A.R. Hoare, 1961)

Wybieramy element środkowy x, przeglądamy tablicę od lewej znajdując a[i]>x i od prawej znajdując a[j]<x, zamieniamy je i kontynuujemy. Wynik: tablica podzielona na dwie części do dalszego sortowania rekurencyjnego.

procedure Sortuj(l, p : Indeks);
var i,j : Indeks; x,y : Obiekt;
begin
  i := l; j := p;
  x := a[(l+p) div 2]; { element srodkowy jako pivot }
  repeat
    while a[i].Klucz < x.Klucz do i := i + 1;
    while x.Klucz < a[j].Klucz do j := j - 1;
    if i <= j then
    begin
      y:=a[i]; a[i]:=a[j]; a[j]:=y;
      i := i+1; j := j-1
    end
  until i > j;
  if l < j then Sortuj(l, j);
  if i < p then Sortuj(i, p)
end;

Procedura wywołuje siebie rekurencyjnie. Ten sam algorytm można zapisać iteracyjnie, zastępując rekurencję przez stos jawny.

10. Sortowanie pozycyjne — radix sort

Wszystkie dotychczasowe metody porównują klucze ze sobą, a dla takich algorytmów udowodniono, że nie da się zejść poniżej n·log(n). Radix sort omija to ograniczenie, bo w ogóle nie porównuje elementów — rozdziela je do kubełków według kolejnych cyfr klucza, od najmniej znaczącej do najbardziej.

Dla liczb 32-bitowych przetwarzanych po bajcie potrzebne są cztery przebiegi po 256 kubełków — czas rośnie liniowo z liczbą elementów.

procedure Pozycyjne;
var i, przesuniecie, cyfra, suma, c : Integer;
    licznik : array[0..255] of Integer;
begin
  przesuniecie := 0;
  while przesuniecie < 32 do
  begin
    for i := 0 to 255 do licznik[i] := 0;

    { ile elementow trafia do kazdego kubelka }
    for i := 1 to n do
    begin
      cyfra := (a[i].Klucz shr przesuniecie) and 255;
      Inc(licznik[cyfra])
    end;

    { zamiana licznikow na pozycje poczatkowe }
    suma := 1;
    for i := 0 to 255 do
    begin
      c := licznik[i]; licznik[i] := suma; suma := suma + c
    end;

    { rozrzut do tablicy pomocniczej - zachowuje stabilnosc }
    for i := 1 to n do
    begin
      cyfra := (a[i].Klucz shr przesuniecie) and 255;
      b[licznik[cyfra]] := a[i];
      Inc(licznik[cyfra])
    end;

    for i := 1 to n do a[i] := b[i];
    przesuniecie := przesuniecie + 8
  end
end;

W pomiarach poniżej to bezkonkurencyjny zwycięzca — przy milionie liczb jest pięciokrotnie szybszy od Quicksorta. Ma jednak istotne ograniczenie: działa tylko dla kluczy, które da się rozłożyć na cyfry o stałej długości (liczby całkowite, daty, teksty stałej długości). Do sortowania po dowolnym kryterium porównawczym się nie nadaje, a przy małych zbiorach narzut na kubełki nie zdąży się zwrócić.

11. Co się stosuje dzisiaj

Żadna z bibliotek standardowych nie używa dziś jednego algorytmu w czystej postaci. Wszystkie są hybrydami, które przełączają metodę zależnie od tego, co zastaną w danych:

• Introsort (C++ std::sort) — startuje jako Quicksort, przy zbyt głębokiej rekurencji przechodzi na heapsort, a krótkie fragmenty (poniżej ~16 elementów) kończy prostym wstawianiem.
• Timsort (Python, Java dla obiektów) — wyszukuje w danych już posortowane fragmenty i scala je ze sobą. Na danych częściowo uporządkowanych — a takie są w praktyce najczęstsze — potrafi zejść do O(n).
• pdqsort (Rust, nowsze wersje C++) — Quicksort z wykrywaniem złośliwych układów danych i powtarzających się kluczy.
• Sortowanie zewnętrzne — gdy dane nie mieszczą się w pamięci, wraca się do scalania: sortuje się porcje mieszczące się w RAM, zapisuje na dysk, a potem scala wielodrożnie.

Wniosek jest ten sam, co dwadzieścia lat temu: nie ma algorytmu najlepszego zawsze. Jest algorytm najlepszy do konkretnych danych — i to ich znajomość, a nie szybkość procesora, decyduje o wyniku.