: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > sortowanie >

S O R T O W A N I E   M E T O D Ą   K O P C A

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Struktura kopca umożliwia stosunkowo szybkie sortowanie liczb w porządku rosnącym - sortowanie w porządku malejącym wymaga stosowania osobnej tablicy wynikowej lub późniejszego odwrócenia tablicy zawierającej kopiec.

Sortowanie polega na cyklicznym usuwaniu z kopca elementu największego, tj. jego korzenia. Po usunięciu korzenia ostatni element kopca przenosimy w miejsce korzenia, zmniejszamy o jeden ilość elementów kopca i ponownie przywracamy jego strukturę: tym razem zaburzenie struktury kopca będzie miało miejsce w korzeniu więc umieszczony w nim element będziemy przemieszczać w dół, aż do momentu, w którym znajdzie się on go we właściwym miejscu.

Type Kopiec = Array[0..1023] Of LongInt;
{Zamień wartości wierzchołków I i J} 
Procedure Zmien(Var Kop : Kopiec; I, J : LongInt);
Var 
  TmpValue : LongInt;
Begin 
 TmpValue:=Kop[I]; 
 Kop[I]:=Kop[J]; 
 Kop[J]:=TmpValue; 
End;
{Sortuj kopiec}
Procedure Sortuj(Var Kop : Kopiec);
Var
  N, K, Ilosc : LongInt;
Begin
  Ilosc:=Kop[0];
  {Usuwaj z kopca kolejno wszystkie elementy}
  While Ilosc>1 Do
    Begin
      {Zmień pierwszy z ostatnim}
      Zmien(Kop, 1, Ilosc);
      Dec(Ilosc);
      N:=1;
      {Przywróć strukturę kopca}
      While 2*N<=Ilosc Do
        Begin
          {Do K wpisz numer większego z następników}
          K:=2*N;
          If K+1<=Ilosc Then
            If Kop[K+1]>Kop[K] Then Inc(K);
          {Jeśli w wierzchołku poddrzewa masz mniej 
	  niż większy syn to zmień}
          If Kop[K]>Kop[N] Then
            Begin
              Zmien(Kop, N, K);
              N:=K;
            End
          Else Break;
        End;
    End;
End;