Sortowanie przez wstawianie

Sortowanie przez wstawianie polega na pobieraniu kolejnych elementów ciągu i poszukaniu dla niego odpowiedniego miejsca na liście elementów uporządkowanych. Gdy miejsce zostanie znalezione, to elementy ww. listy się rozsuwa i w tak ustalone miejsce wkłada element.

Założenie: ciąg liczb do sortowania: 4,1,6,3

Realizacja:
4 1 6 | 3 - element ostatni jest początkiem listy uporządkowanej

wybiera się element leżący tuż przed elementem ostatnim (liczba 6) i porównuje się

z elementem listy (3)

element 6>3 zatem   
4 1 | 3 6

wybiera się następny element (1), i porównuje z elementami listy oraz odpowiednio

"wkłada"   
4 | 1 3 3    itd.

Przykładowa realizacja ww. algorytmu w języku Turbo Pascal:

program sortowanie_przez_wstawianie;
uses crt;
const n=10;
var
  tab:array[1..n] of integer;
  i,j,k : integer;
begin
  clrscr;
  writeln('Sortowanie przez wstawianie');
  for i:= 1 to n do readln(tab[i]);
  writeln('Liczby przed sortowaniem:');
  for i:= 1 to n do write(tab[i]);
  for j:=n-1 downto 1 do
  begin
    k := tab[j];
    i := j + 1;
    while (i<=n) and (k>tab[i]) do
    begin
      tab[i-1]:=tab[i];
      i:=i+1;
    end;
    tab[i-1]:=k;
  end;
  writeln('Liczby po sortowaniu:');
  for i:=1 to n do write(tab[i]);
  repeat until keypressed;
end.
  • Sortowanie przez wybór
  • Sortowanie bąbelkowe
  • Sortowanie przez scalanie

Komentarze


link Silnią liczby naturalnej n nazywamy iloczyn wszystkich liczb naturalnych nie większych niż n. Oznaczenie symboliczne n! (czytaj: n silnia) wprowadził w 1808 roku francuski matematyk Christian Kramp. Zgo


link Ciąg Fibonacciego to ciąg liczb naturalnych zwanych liczbami Fibonacciego określony rekurencyjnie w sposób następujący:F0 = 0F1 = 1Fn = Fn-1 + Fn-2, dla n ≥ 2Początkowe wartości tego ciągu to:


link Sito Eratostenesa jest sposobem wyznaczania liczb pierwszych zaproponowanym przez greckiego matematyka Eratostenesa. Metoda sita (w założeniu eliminacja) polega na odrzucaniu liczb naturalnych będących wielokrotnościami liczb pie


link program kwadratowe;uses crt;var x1,x2,x,r1,r2,delta,pierwiastek:real;    a,b,c,yw,x0:real;    kla:char;beginrepeat  clrscr;  writeln('Ten program rozwiazuje rownania kwadratowe axx+by+c');  w