Sortowanie Przez Wstawianie
Sortowanie przez wstawianie (ang. ''Insert Sort'', ''Insertion Sort'')
prosty algorytm sortowania, o złożoności O(n2). Mimo że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy heapsort posiada pewne zalety:
  • wydajny dla danych wstępnie posortowanych
  • wydajny dla zbiorów o niewielkiej liczebności
  • stabilny

Algorytm polega na usuwaniu pewnego elementu z danych wejściowych i wstawianiu go na odpowiednie miejsce w wynikach. Wybór następnego elementu z danych jest dowolny.

Schemat działania algorytmu

  1. Utwórz zbiór elementów posortowanych i przenieś do niego dowolny element ze zbioru nieposortowanego.
  2. Weź dowolny element ze zbioru nieposortowanego.
  3. Wyciągnięty element porównuj z kolejnymi elementami zbioru posortowanego póki nie napotkasz elementu równego lub elementu większego (jeśli chcemy otrzymać ciąg niemalejący) lub nie znajdziemy się na początku/końcu zbioru uporządkowanego.
  4. Wyciągnięty element wstaw w miejsce gdzie skończyłeś porównywać.
  5. Jeśli zbiór elementów nieuporządkowanych jest niepusty wróć do punkt 2.

Kod w Pascalu

const
  n=100;
var
  i,j,wartownik:integer;
  tab:array[1..n]of integer;
BEGIN
  randomize;
  for i:=1 to n do tab[i]:=random(n);
  for j:=n-1 downto 1 do begin
    wartownik:=tab[j];
    i:=j+1;
    while (i<=n)and( wartownik >tab[i]) do begin
      tab[i-1] := tab[i];
      inc(i);
    end;
    tab[i-1] := wartownik;
  end;
  for i:=1 to n do write(tab[i], ' ');
END.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License