Sortowanie przez wstawianie
           Insertion Sort


Podrozdziały     Tematy pokrewne

Algorytm

Algorytm sortowania przez wstawianie można porównać do sposobu układania kart pobieranych z talii. Najpierw bierzemy pierwszą kartę. Następnie pobieramy kolejne, aż do wyczerpania talii. Każdą pobraną kartę porównujemy z kartami, które już trzymamy w ręce i szukamy dla niej miejsca przed pierwszą kartą starszą (młodszą w przypadku porządku malejącego). Gdy znajdziemy takie miejsce, rozsuwamy karty i nową wstawiamy na przygotowane w ten sposób miejsce (stąd pochodzi nazwa algorytmu - sortowanie przez wstawianie, ang. Insertion Sort). Jeśli nasza karta jest najstarsza (najmłodsza), to umieszczamy ją na samym końcu. Tak porządkujemy karty. A jak przenieść tę ideę do świata komputerów i zbiorów liczbowych?

Algorytm sortowania przez wstawianie będzie składał się z dwóch pętli. Pętla główna (zewnętrzna) symuluje pobieranie kart, czyli w tym wypadku elementów zbioru. Odpowiednikiem kart na ręce jest tzw. lista uporządkowana (ang. sorted list), którą sukcesywnie będziemy tworzyli na końcu zbioru (istnieje też odmiana algorytmu umieszczająca listę uporządkowaną na początku zbioru). Pętla sortująca (wewnętrzna) szuka dla pobranego elementu miejsca na liście uporządkowanej. Jeśli takie miejsce zostanie znalezione, to elementy listy są odpowiednio rozsuwane, aby tworzyć miejsce na nowy element i element wybrany przez pętlę główną trafia tam. W ten sposób lista uporządkowana rozrasta się. Jeśli na liście uporządkowanej nie ma elementu większego od wybranego, to element ten trafia na koniec listy. Sortowanie zakończymy, gdy pętla główna wybierze wszystkie elementy zbioru.

Algorytm sortowania przez wstawianie posiada klasę czasowej złożoności obliczeniowej równą O(n2). Sortowanie odbywa się w miejscu.

 

Wstawianie elementu na listę uporządkowaną

Najważniejszą operacją w opisywanym algorytmie sortowania jest wstawianie wybranego elementu na listę uporządkowaną. Zasady są następujące:

  1. Na początku sortowania lista uporządkowana zawiera tylko jeden, ostatni element zbioru. Jednoelementowa lista jest zawsze uporządkowana.
  2. Ze zbioru zawsze wybieramy element leżący tuż przed listą uporządkowaną. Element ten zapamiętujemy w zewnętrznej zmiennej. Miejsce, które zajmował, możemy potraktować jak puste.

  3. Wybrany element porównujemy z kolejnymi elementami listy uporządkowanej.

  4. Jeśli natrafimy na koniec listy, element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.

  5. Jeśli element listy jest większy od wybranego, to element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.

  6. Jeśli element listy nie jest większy od wybranego, to element listy przesuwamy na puste miejsce. Dzięki tej operacji puste miejsce wędruje na liście przed kolejny element. Kontynuujemy porównywanie, aż wystąpi sytuacja z punktu 4 lub 5.

Przykład:

Dla przykładu wstawmy wg opisanej metody pierwszy element zbioru listę uporządkowaną utworzoną z pozostałych elementów {8 4 5 6 9}. Elementy listy uporządkowanej zaznaczyliśmy kolorem zielonym. Puste miejsce zaznaczyliśmy kolorem białym:

 

Zbiór Opis operacji
 8  4  5  6  9 
Element 8 znajduje się tuż przed listą uporządkowaną.
 8 
    4  5  6  9 
Wybieramy ze zbioru element 8. Zajmowane przez niego miejsce staje się puste.
    8 
    5  6  9 
Porównujemy 8 z pierwszym elementem listy uporządkowanej, z liczbą 4.
    8 
<<< 5  6  9 
Ponieważ element 4 jest mniejszy od elementu wybranego 8, przesuwamy go na puste miejsce. Zwróć uwagę, iż puste miejsce wędruje w kierunku końca listy uporządkowanej.
       8 
    5  6  9 
Porównujemy 8 z kolejnym elementem listy uporządkowanej, z liczbą 5.
       8 
 5 <<< 6  9 
5 jest5 mniejsze od 8, zatem wędruje na puste miejsce, które przesuwa się przed kolejny element listy uporządkowanej, liczbę 6.
          8 
 4  5     6  9 
Porównujemy 8 z 6.
          8 
 4  5  6 <<< 9 
6 jest mniejsze od 8, wędruje na puste miejsce.
             8 
 4  5  6     9 
Porównujemy 8 z 9.
 4  5  6  8  9 
Tym razem element wybrany wędruje na puste miejsce, ponieważ jest mniejszy od elementu 9 listy uporządkowanej. Operacja wstawiania jest zakończona. Lista rozrasta się o jeden element.

 

Przykład:

Wykorzystajmy podane informacje do posortowania opisywaną metodą zbioru { 7 3 8 5 2 }.

 

Zbiór Opis operacji
 7  3  8  5  2 
Ostatni element jest zalążkiem listy uporządkowanej.
          5 
 7  3  8     2 
Ze zbioru wybieramy element leżący tuż przed listą uporządkowaną.
             5 
 7  3  8     2 
Wybrany element porównujemy z elementem listy.
             5 
 7  3  8  2 <<<
Ponieważ element listy jest mniejszy od elementu wybranego, to przesuwamy go na puste miejsce.
 7  3  8  2 
Na liście nie ma już więcej elementów do porównania, więc element wybrany wstawiamy na puste miejsce. Lista uporządkowana zawiera już dwa elementy.
       8 
 7  3     2  5 
Ze zbioru wybieramy 8
          8 
 7  3     2 
8 porównujemy z 2
          8 
 7  3  2 <<<
2 jest mniejsze, zatem przesuwamy je na puste miejsce.
             8 
 7  3  2    
8 porównujemy z 5
             8 
 7  3  2 <<<
5 jest mniejsze, przesuwamy je na puste miejsce
 7  3  2   8 
Lista nie zawiera więcej elementów, zatem 8 wstawiamy na puste miejsce. Na liście uporządkowanej mamy już trzy elementy.
    3 
 7     2  5  8 
Ze zbioru wybieramy 3
       3 
 7     2  5  8 
3 porównujemy z 2
       3 
 7  2 <<< 5  8 
2 jest mniejsze, wędruje zatem na puste miejsce
          3 
 7  2     8 
3 porównujemy z 5.
 7  2  3  5  8 
Tym razem mniejszy jest element wybrany. Znaleźliśmy jego miejsce na liście, więc wstawiamy go na puste miejsce. Lista zawiera już 4 elementy.
 7 
    2  3  5  8 
Ze zbioru wybieramy ostatni element - liczbę 7.
    7 
    2  3  5  8 
7 porównujemy z 2
    7 
 2 <<< 3  5  8 
2 jest mniejsze, przesuwamy je na puste miejsce
       7 
 2     3  5  8 
7 porównujemy z 3
       7 
 2  3 <<< 5  8 
3 jest mniejsze, przesuwamy je na puste miejsce
          7 
 2  3     8 
7 porównujemy z 5
          7 
 2  3 <<< 8 
5 jest mniejsze, przesuwamy je na puste miejsce
             7 
 2  3  5     8 
7 porównujemy z 8
 2  3  5  7  8 
Element wybrany jest mniejszy, wstawiamy go na puste miejsce. Lista uporządkowana objęła już cały zbiór. Sortowanie jest zakończone.

 

Specyfikacja problemu

Dane wejściowe

n - liczba elementów w sortowanym zbiorze, n N
d[ ] - zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.

Dane wyjściowe

d[ ] - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.

Zmienne pomocnicze

i, j - zmienne sterujące pętli, i, j N
x - zawiera wybrany ze zbioru element.

 

Lista kroków

K01: Dla j = n - 1, n - 2, ..., 1: wykonuj K02...K04
K02:     x ← d[j];  ij + 1
K03:     Dopóki ( in )  ∧  ( x > d[i] ): wykonuj d[i - 1] ← d[i];  ii + 1
K04:     d[i - 1] ← x
K05: Zakończ

 

Schemat blokowy

flow

Pętlę główną rozpoczynamy od przedostatniej pozycji w zbiorze. Element na ostatniej pozycji jest zalążkiem listy uporządkowanej. Dlatego licznik pętli nr 1 przyjmuje wartość początkową j = n - 1.

Ze zbioru wybieramy element d[j] i umieszczamy go w zmiennej pomocniczej x. Miejsce zajmowane przez ten element staje się puste.

 

Uwaga techniczna

W rzeczywistości na pozycji j pozostaje dalej ten sam element. Jednakże zapamiętaliśmy jego wartość, zatem pozycja ta może być zapisana inną informacją - elementu nie utracimy, ponieważ przechowuje go zmienna x. Dlatego pozycję tę możemy potraktować jako pustą, tzn. z nieistotną zawartością.

 

Pętlę wewnętrzną rozpoczynamy od pozycji następnej w stosunku do j. Pozycja ta zawiera pierwszy element listy uporządkowanej, która tworzona jest na końcu sortowanego zbioru. Pętlę wewnętrzną przerywamy w dwóch przypadkach - gdy licznik pętli wyjdzie poza indeks ostatniego elementu w zbiorze lub gdy element wybrany, przechowywany w zmiennej pomocniczej x, jest mniejszy lub równy bieżąco testowanemu elementowi listy uporządkowanej (dla sortowania malejącego należy zastosować w tym miejscu relację większy lub równy). W obu przypadkach na puste miejsce ma trafić zawartość zmiennej x i pętla zewnętrzna jest kontynuowana. Zauważ, iż pozycja tego miejsca w zbiorze jest równa i - 1.

Jeśli żaden z warunków przerwania pętli wewnętrznej nr 2 nie wystąpi, to przesuwamy bieżący element listy na puste miejsce i kontynuujemy pętlę wewnętrzną.

Podsumowując: pętla zewnętrzna wybiera ze zbioru kolejne elementy o indeksach od n - 1 do 1, pętla wewnętrzna szuka dla wybranych elementów miejsca wstawienia na liście uporządkowanej, po znalezieniu którego pętla zewnętrzna wstawia wybrany element na listę. Gdy pętla zewnętrzna przebiegnie wszystkie elementy o indeksach od n - 1 do 1, zbiór będzie posortowany.

Algorytm posiada klasę czasowej złożoności obliczeniowej równą O(n2). Sortowanie odbywa się w miejscu.

 

Programy

Efekt uruchomienia programu
 Sortowanie przez wstawianie
-----------------------------
   (C)2005  Jerzy Walaszek

Przed sortowaniem:

  56   5  18  74  83  24  13   4  50  74  63  83  65  65  63  40  81  69  60  84

Po sortowaniu:

   4   5  13  18  24  40  50  56  60  63  63  65  65  69  74  74  81  83  83  84

 

DevPascal
// Sortowanie Przez Wstawianie
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

program Insertion_Sort;

const N = 20; // Liczebność zbioru.

var
  d : array[1..N] of integer;

// Program główny
//---------------

var
  i,j,x : integer;
begin
  writeln(' Sortowanie przez wstawianie ');
  writeln('-----------------------------');
  writeln('   (C)2005  Jerzy Walaszek   ');
  writeln;

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
// a następnie wyświetlamy jej zawartość

  randomize;
  for i := 1 to N do d[i] := random(100);
  writeln('Przed sortowaniem:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  writeln;

// Sortujemy

  for j := N - 1 downto 1 do
  begin
    x := d[j];
    i := j + 1;
    while (i <= N) and (x > d[i]) do
    begin
      d[i - 1] := d[i];
      inc(i);
    end;
    d[i - 1] := x;
  end;

// Wyświetlamy wynik sortowania

  writeln('Po sortowaniu:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  writeln;
  writeln('Nacisnij Enter...');
  readln;
end.
Code::Blocks
// Sortowanie Przez Wstawianie
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 20; // Liczebność zbioru.

// Program główny
//---------------

int main()
{
  int d[N],i,j,x;
  
  cout << " Sortowanie przez wstawianie\n"
          "-----------------------------\n"
          "   (C)2005  Jerzy Walaszek\n\n"
          "Przed sortowaniem:\n\n";

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
// a następnie wyświetlamy jej zawartość

  srand((unsigned)time(NULL));

  for(i = 0; i < N; i++) d[i] = rand() % 100;
  for(i = 0; i < N; i++) cout << setw(4) << d[i];
  cout << endl;

// Sortujemy

  for(j = N - 2; j >= 0; j--)
  {
    x = d[j];
    i = j + 1;
    while((i < N) && (x > d[i]))
    {
      d[i - 1] = d[i];
      i++;
    }
    d[i - 1] = x;
  }

// Wyświetlamy wynik sortowania

  cout << "Po sortowaniu:\n\n";
  for(i = 0; i < N; i++) cout << setw(4) << d[i];
  cout << endl;
  return 0;
}
Free Basic
' Sortowanie Przez Wstawianie
'--------------------------------------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'--------------------------------------------------------

  OPTION EXPLICIT
  
  CONST N = 20 ' Liczebność zbioru.

  DIM d(1 TO N) AS INTEGER
  DIM i AS INTEGER, j AS INTEGER, x AS INTEGER

  PRINT " Sortowanie przez wstawianie "
  PRINT "-----------------------------"
  PRINT "   (C)2005  Jerzy Walaszek   "
  PRINT

' Najpierw wypełniamy tablicę d() liczbami pseudolosowymi
' a następnie wyświetlamy jej zawartość

  RANDOMIZE TIMER
  FOR i = 1 TO N: d(i) = INT(RND * 100): NEXT
  PRINT "Przed sortowaniem:"
  PRINT
  FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
  PRINT

' Sortujemy

  FOR j = N - 1 TO 1 STEP -1
    x = d(j)
    i = j + 1
    WHILE (i <= N) AND (x > d(i))
      d(i - 1) = d(i)
      i = i + 1
    WEND
    d(i - 1) = x
  NEXT

' Wyświetlamy wynik sortowania

  PRINT "Po sortowaniu:"
  PRINT
  FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
  PRINT
  PRINT "Nacisnij Enter..."
  SLEEP
  END
JavaScript
<html>
  <head>
  </head>
  <body>
    <form style="BORDER-RIGHT: #ff9933 1px outset;
                 PADDING-RIGHT: 4px; BORDER-TOP: #ff9933 1px outset;
                 PADDING-LEFT: 4px; PADDING-BOTTOM: 1px;
                 BORDER-LEFT: #ff9933 1px outset; PADDING-TOP: 1px;
                 BORDER-BOTTOM: #ff9933 1px outset;
                 BACKGROUND-COLOR: #ffcc66" name="frminsertionsort">
      <h3 style="text-align: center">Sortowanie Przez Wstawianie</h3>
      <p style="TEXT-ALIGN: center">
        (C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie
      </p>
      <hr>
      <p style="TEXT-ALIGN: center">
        <input onclick="main()" type="button" value="Sortuj" name="B1">
      </p>
      <p id="t_out" style="TEXT-ALIGN: center">...</p>
    </form>

<script language=javascript>

// Sortowanie Przez Wstawianie
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

var N = 20; // Liczebność zbioru.

function main()
{
  var d = new Array(N);
  var i,j,x,t;

  // Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi

  for(i = 0; i < N; i++) d[i] = Math.floor(Math.random() * 100);
  t = "Przed sortowaniem:<BR><BR>";
  for(i = 0; i < N; i++) t += d[i] + " ";
  t += "<BR><BR>";

  // Sortujemy

  for(j = N - 2; j >= 0; j--)
  {
    x = d[j];
    i = j + 1;
    while((i < N) && (x > d[i]))
    {
      d[i - 1] = d[i];
      i++;
    }
    d[i - 1] = x;
  }

  // Wyświetlamy wynik sortowania

  t += "Po sortowaniu:<BR><BR>";
  for(i = 0; i < N; i++) t += d[i] + " ";
  document.getElementById("t_out").innerHTML = t;
}

</script> 

  </body>
</html>

 

Tutaj możesz przetestować działanie prezentowanego skryptu:

Sortowanie Przez Wstawianie

(C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie


...

 

Einstein
DLA
GENIUSZA

Badania algorytmów sortowania

W celach badawczych testujemy czas wykonania algorytmu sortowania przez wstawianie w środowisku opisanym we wstępie. Program testujący jest następujący:

 

DevPascal
// Program testujący czas sortowania dla
// danego algorytmu sortującego
//--------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie
//--------------------------------------

program TestCzasuSortowania;

uses Windows;

const
  NAZWA = 'Sortowanie przez wstawianie';
  K1    = '--------------------------------------------------';
  K2    = '(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie';
  K3    = '------n---------tpo---------tod---------tpp---------tpk---------tnp';
  K4    = '-------------------------------------------------------------------';
  MAX_LN = 6; // określa ostatnie LN
  LN : array[1..8] of integer = (1000,2000,4000,8000,16000,32000,64000,128000);

var
  d         : array[1..128000] of real; // sortowana tablica
  n         : integer;                  // liczba elementów
  qpf,tqpc  : int64;                    // dane dla pomiaru czasu
  qpc1,qpc2 : int64;

// Tutaj umieszczamy procedurę sortującą tablicę d
//-------------------------------------------------------
function Sort : extended;
var
  i,j : integer;
  x        : real;
begin
  QueryPerformanceCounter(addr(qpc1));
  for j := n - 1 downto 1 do
  begin
    x := d[j];
    i := j + 1;
    while (i <= n) and (x > d[i]) do
    begin
      d[i - 1] := d[i];
      inc(i);
    end;
    d[i - 1] := x;
  end;
  QueryPerformanceCounter(addr(qpc2));
  Sort := (qpc2 - qpc1 - tqpc) / qpf;
end;

// Program główny
//---------------
var
  i,j,k               : integer;
  tpo,tod,tpp,tpk,tnp : extended;
  f                   : Text;
begin
  if QueryPerformanceFrequency(addr(qpf)) then
  begin
    QueryPerformanceCounter(addr(qpc1));
    QueryPerformanceCounter(addr(qpc2));
    tqpc := qpc2 - qpc1;

    assignfile(f,'wyniki.txt'); rewrite(f);

// Wydruk na ekran

    writeln('Nazwa: ',NAZWA);
    writeln(K1);
    writeln(K2);
    writeln;
    writeln(K3);

// Wydruk do pliku

    writeln(f,'Nazwa: ',NAZWA);
    writeln(f,K1);
    writeln(f,K2);
    writeln(f,'');
    writeln(f,K3);
    for i := 1 to MAX_LN do
    begin
      n := LN[i];

// Czas sortowania zbioru posortowanego

      for j := 1 to n do d[j] := j;
      tpo := Sort;

// Czas sortowania zbioru posortowanego odwrotnie

      for j := 1 to n do d[j] := n - j;
      tod := Sort;

// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na początku - średnia z 10 obiegów

      tpp := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := k;
        d[1] := random * n + 1;
        tpp += Sort;
      end;
      tpp /= 10;

// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na końcu - średnia z 10 obiegów

      tpk := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := k;
        d[n] := random * n + 1;
        tpk += Sort;
      end;
      tpk /= 10;

// Czas sortowania zbioru nieuporządkowanego - średnia z 10 obiegów

      tnp := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := random;
        tnp += Sort;
      end;
      tnp /= 10;

      writeln(n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
      writeln(f,n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
    end;
    writeln(K4);
    writeln(f,K4);
    writeln(f,'Koniec');
    closefile(f);
    writeln;
    writeln('Koniec. Wyniki w pliku WYNIKI.TXT');
  end
  else writeln('Na tym komputerze program testowy nie pracuje !');
  writeln;
  write('Nacisnij klawisz ENTER...'); readln;
end.

 

Otrzymane wyniki są następujące (dla komputera o innych parametrach wyniki mogą się różnić co do wartości czasów wykonania, dlatego w celach porównawczych proponuję uruchomić podany program na komputerze czytelnika):

 

Zawartość pliku wygenerowanego przez program
Nazwa: Sortowanie przez wstawianie
--------------------------------------------------
(C)2011/2012 I Liceum Ogolnoksztalcace w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
1000 0.000040 0.005941 0.000060 0.000074 0.002360
2000 0.000080 0.017525 0.000088 0.000113 0.009178
4000 0.000159 0.069866 0.000175 0.000218 0.035947
8000 0.000318 0.290939 0.000387 0.000382 0.141822
16000 0.000671 1.129738 0.000790 0.000842 0.572611
32000 0.001324 5.284645 0.001525 0.001644 2.443392
-------------------------------------------------------------------
Koniec

Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):

n -  ilość elementów w sortowanym zbiorze
tpo -  czas sortowania zbioru posortowanego
tod -  czas sortowania zbioru posortowanego malejąco
tpp -  czas sortowania zbioru posortowanego z losowym elementem na początku
tpk -  czas sortowania zbioru posortowanego z losowym elementem na końcu
tnp -  czas sortowania zbioru z losowym rozkładem elementów

(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)

(Arkusz kalkulacyjny Excel do wyznaczania wzrostu prędkości sortowania)

Podsumowanie

Analizując wyniki obliczeń w arkuszu kalkulacyjnym otrzymanych czasów sortowania dla algorytmu sortowania przez wstawianie wyciągamy następujące wnioski:

 

Cechy Algorytmu Sortowania Przez Wstawianie
klasa złożoności obliczeniowej optymistyczna O(n)
klasa złożoności obliczeniowej typowa O(n2)
klasa złożoności obliczeniowej pesymistyczna O(n2)
Sortowanie w miejscu TAK
Stabilność TAK

 

Klasy złożoności obliczeniowej szacujemy następująco:

Własności algorytmu
Algorytm tpo tod tpp tpk tnp
Sortowanie przez wstawianie O(n) O(n2) O(n) O(n) O(n2)
tpo << tod tpp tpk
tnp   1 tod
2
  1. Algorytm wykorzystuje fakt posortowania zbioru. Dla zbiorów w znacznym stopniu uporządkowanych klasa czasowej złożoności obliczeniowej algorytmu jest prawie liniowa. Czas sortowania takich zbiorów jest bardzo krótki.
  2. Najbardziej niekorzystnym przypadkiem jest sortowanie zbioru posortowanego odwrotnie - czas sortowania jest najdłuższy. Czas sortowania zbioru o losowym rozkładzie elementów jest o połowę krótszy.
Wzrost prędkości sortowania
Algorytmy tpo tod tpp tpk tnp

Sortowanie przez wybór

Sortowanie przez wstawianie

  3 n
40
dobrze
  2
3
źle
  2 n
30
dobrze
  3 n
50
dobrze
  4
3
dobrze
  1. Analiza wzrostu prędkości algorytmu sortowania przez wstawianie w stosunku do algorytmu sortowania przez wybór pokazuje, iż obecny algorytm jest dużo lepszy w przypadku zbiorów w znacznym stopniu uporządkowanych. Również zbiory o losowym rozkładzie elementów będą posortowane szybciej. Jedynie w przypadku pesymistycznym, gdy zbiór jest posortowany odwrotnie, algorytm jest wolniejszy od algorytmu sortowania przez wybór. Te cechy czynią algorytm sortowania przez wstawianie zalecanym, prostym algorytmem sortującym klasy O(n2).

Zadania dla ambitnych

  1. Porównaj wzrost prędkości algorytmu sortowania przez wstawianie z algorytmem sortowania bąbelkowego w wersji nr 4. Wyciągnij odpowiednie wnioski.
  2. Udowodnij, iż algorytm ma liniową klasę czasowej złożoności obliczeniowej przy sortowaniu zbiorów uporządkowanych z jednym elementem nie na swoim miejscu.
  3. Wyznacz liczbę porównań przy sortowaniu n-elementowego (n > 1) zbioru uporządkowanego z wyjątkiem ostatniego elementu, który jest mniejszy od wszystkich pozostałych elementów zbioru.
  4. Wyznacz liczbę przesunięć elementów listy uporządkowanej przy sortowaniu n-elementowego (n > 1) zbioru posortowanego odwrotnie.

Zobacz również na: wersję z wyszukiwaniem binarnym

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.