Pivotsortering :-)

[gimpster]

Hvis dette virker, s� er vi heldige :-)

/Martin



procedure pivotsortering(var liste: henv);
var
  element, stoerre, lavere : henv;
begin
  { hvis liste kun indeholder �t element, s� er vi f�rdige }
  if (liste = nil) then
    exit;

  { disse lister er tomme fra starten }
  stoerre := nil;
  lavere  := nil;

  { sk�rer pivot v�k }
  pivot   := fjern_pivot(liste);

  element := liste;

  { vi lader element l�be igennem listen }
  while element <> nil do
  begin
    if element^.noegle < pivot^.noegle then
    begin { elementet er mindre end vores pivot }
      { vi kobler elementet ind i starten af lavere }
      element^.naeste := lavere;
      lavere          := element;
    end
    else
    begin { elementet er st�rre end vores pivot }
      { vi kobler elementet ind i starten af st�rre }
      element^.naeste := stoerre;
      stoerre         := element;
    end;
  end;

  { s� skal lavere sorteres... }
  pivotsortering(lavere);
  { og det skal st�rre ogs� }
  pivotsortering(stoerre);

  { vi s�tter listerne sammen, s� lavere kommer f�rst,
    s� pivot og til sidst st�rre }
  liste   := lavere;
  element := lavere;
  { vi skal finde det sidste element i listen... }
  while element^.naeste <> nil do
    elememt := element^.naeste;
  
  { ...s�dan at vi kan s�tte det til at pege p� vores pivot }
  element^.naeste := pivot;
  pivot^.naeste   := stoerre;

end;

{ Finder og fjerner pivot fra liste }
function fjern_pivot(var liste : henv): henv;
begin
  result := liste;
  liste  := liste^.naeste;
end;