Sortowanie stosu przez selekcje

W internecie, jak i na 4p jest opisanych sporo metod sortowania. Jednak najczęsciej odbywa się to na przykładzie tablicy.
Ale jak posortować strukturę dynamiczną, jaką np. jest stos?
Okazuje się, że zaimplementowanie algorytmu QuickSort dla stosu jest dosyć kłopotliwe.
QuickSort przeszukuje ciąg jednocześnie z klilku stron. W stosie żeby "dostać się" np. do elementu środkowego, musimy "przelecieć" po wskaźnikach od pierwszego elementu, co znacznie spowalnia sortowanie.

Z pomocą przychodzą nam jednak najprostsze rozwiązania. Sortowanie przez selekcję lub bąbelkowe nigdy nie uchodziły za najszybsze :) jednak jeśli chodzi o listy, nadają się idealnie.

Oto implementacja sortowania przez wymianę w Pascalu:

type
  wsk = ^Lista;
  Lista = record
    dane : integer;
    nast : wsk;
  end;

var
  Wierzch : wsk = nil;

procedure Sort;
var
  W,V, WMin : Wsk;
  Min, tmp : integer;
begin
  V := Wierzch;
  // przeszukuje od wierzchu do spodu, czyli wartosci NIL
  while V<>nil do begin
    Min := V^.dane;
    W := V^.nast;
    // w tej pętli wyszukuje elementu mniejszego od V
    while W<>nil do begin
      if W^.dane < Min then begin
        Min := W^.dane;
        WMin := W;
      end;
      W := W^.nast;
    end;
    // jeśli znalazł element mniejszy zamienia go z V
    if Min < V^.dane then begin
      tmp := V^.dane;
      V^.dane := WMin^.dane;
      WMin^.dane := tmp;
    end;
    V := V^.nast;
  end;
end;

Przy czym ten algorytm sortuje przez zamienę samych wartości, a nie wskaźników. Zamiana przez wskaźniki jest trochę bardziej skomplikowana, ale jeśli przechowujemy w listach coś większego niż liczbę to okaże się to bardziej wydajny sposób sortowania.
Postaram się go w najbliższym czasie dodać do tego artykułu.