: 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   P R Z E Z   W S T A W I A N I E

 

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

 
       

Sortowanie przez wstawianie jest algorytmem porządkującym ciąg elementów rosnąco (lub majejąco) o złożoności pesymistycznej O(n2). Przy losowych danych może okazać się znacznie szybsze od [ sortowania bąbelkowego ].

Jeżeli w tablicy liczby od miejsca 1 do miejsca i-1 są już posortowane rosnąco, to możemy otrzymać fragment posortowany do miejsca i wstawiając liczbę z miejsca i w odpowiednie miejsce tablicy, zaś pozostałe liczby rozsunąć (przesunąć w prawo o jedną komórkę):

tablica posortowana do miejsca 6
tablica                 : 1 2 4 6 8 9 | 3
liczba do wstawienia    : 3

każdą liczbę od miejsca 6 do miejsca 3 przesuwamy o jedną komórkę w prawo
tablica po rozsunięciu  : 1 2 4 4 6 8 | 9
tablica po wstawieniu 3 : 1 2 3 4 6 8 | 9

 

  1. Dla wszystkich i z zakresu od 2 do n:

    • liczby tablicy od miejsca 1 do miejsca i-1 są już posortowane, liczbę z miejsca i należy wstawić w takie miejsce k, aby wszystkie liczby od miejsca 1 do miejsca i tworzyły ciąg rosnący, co wymaga "rozsunięcia" ciągu, tj. przesunięcia wszystkich liczb od miejsca k do miejsca i-1 o jedną pozycję w prawo,

    • przechowaj wartość liczby z miejsca i,

    • wyznacz miejsce k przesuwając przy tym liczby z miejsc i-1, i-2, ..., k o jedno miejsce w prawo,

    • zapisz przechowaną liczbę na miejscu k.

Type
  Tablica = Array[1..1000] Of Integer;


Procedure Sort(Var a : Tablica; n : Integer);
Var
  i, k, tmp : Integer;
Begin
  For i:=2 To n Do
    Begin
      tmp:=a[i];
      k:=i-1;
      While (k>0) And (a[k]>tmp) Do
        Begin
          a[k+1]:=a[k];
          k:=k-1;
        End;
      a[k+1]:=tmp;
    End;
End;

Najbadziej niekorzystny czas sortowania wystąpi, gdy ciąg jest uporządkowany malejąco, dla ciągu uporządkowanego rosnąco złożoność wynosi tylko O(n).