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
- Utwórz zbiór elementów posortowanych i przenieś do niego dowolny element ze zbioru nieposortowanego.
- Weź dowolny element ze zbioru nieposortowanego.
- 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.
- Wyciągnięty element wstaw w miejsce gdzie skończyłeś porównywać.
- 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.
Podobne strony
Podobne Strony • Szyfr Cezara • Hello World • Sortowanie Przez Kopcowanie • Sortowanie Babelkowe • Rok Przestepny • Wieża hanoi • wyswietlanie liczby calkowitej metodą odejmowania poteg • Parzysta Nieparzysta • Ruchoma Gwiazdka • Sortowanie Przez Wybieranie • QuickSort • Nww • Metoda Babelkowa • Silnia • Miejsca Zerowe Funkcji Kwadratowej • Fibonacci
wersja strony: 3, ostatnia edycja: 27 Apr 2009 20:23