Algorytmy Sortujące - Binarne Sortowanie przez Wstawianie

Algorytm sortowania przez wstawianie wykorzystuje poszukiwanie liniowe w celu znalezienia miejsca wstawiania wybranego elementu na liście uporządkowanej. Są trzy możliwości:

Element wybrany jest mniejszy lub równy pierwszemu elementowi listy uporządkowanej (w porządku malejącym element ten jest większy lub równy). W takim przypadku wykonane zostanie tylko jedno porównanie i element wybrany wróci z powrotem na swoje poprzednie miejsce.
Element wybrany jest większy od ostatniego elementu listy uporządkowanej (w porządku malejącym element wybrany jest mniejszy od ostatniego elementu listy uporządkowanej). Jeśli element wybrany znajduje się na j-tej pozycji, to algorytm musi wykonać (n - j) porównań elementy wybranego z kolejnymi elementami listy oraz tyle samo przesunięć elementów listy na puste miejsce.
W pozostałych przypadkach element wybrany trafia do wnętrza listy uporządkowanej. Statystycznie będzie to jej środek, zatem średnio algorytm wykona 0,5 • (n - j) porównań i przesunięć elementów.

Ponieważ lista jest uporządkowana, możemy do jej przeszukania wykorzystać algorytm wyszukiwania binarnego, który ma klasę czasowej złożoności obliczeniowej równą O(logn), jest zatem niesamowicie szybki. Zasada przeszukiwania binarnego jest bardzo prosta. Wyznaczamy element środkowy listy. Sprawdzamy, czy wstawiany element jest mniejszy lub równy (przy sortowaniu malejącym większy lub równy) od elementu środkowego listy. Jeśli tak, to za nowy przedział przyjmujemy pierwszą część listy, w przeciwnym razie drugą. Operację tę powtarzamy dotąd, aż przedział poszukiwań skurczy się do 1 elementu (nie można wtedy wyznaczać połówek). Pozycja tego elementu wyznaczy nam miejsce wstawienia. Musimy tylko przesunąć o jedną pozycję wstecz wszystkie elementy od pozycji (j + 1) do znalezionego miejsca na liście, a następnie wstawić na zwolnione miejsce element wybrany.

Brzmi super - zmniejszymy liczbę porównań. Czy jest to jednak opłacalne, zobaczymy później, po analizie czasów wykonania algorytmu.

do podrozdziału do strony

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	- indeks środkowego elementu listy uporządkowanej, i ∈ N
j	- licznik obiegów pętli zewnętrznej, indeks wybranego elementu, j ∈ N
i_p, i_k	- początkowa i końcowa pozycja indeksów w partycji listy uporządkowanej, i_p, i_k ∈ N
x	- zawiera wybrany ze zbioru element

Lista kroków

K01:	Dla j = n - 1, n - 2,...,1: wykonuj kroki K02...K07
K02:	x ← d[j]; i_p ← j; i_k ← n + 1
K03:	Dopóki i_k - i_p > 1: wykonuj kroki K04...K05
K04:	i ← (i_p + i_k) div 2
K05:	Jeśli x ≤ d[i], to i_k ← i inaczej i_p ← i
K06:	Dla i = j, j + 1, ..., i_p - 1: wykonuj d[i] ← d[i + 1]
K07:	d[i_p] ← x
K08:	Zakończ

Schemat blokowy

obrazek

Algorytm zoptymalizowanego sortowania przez wstawianie zbudowany jest z trzech pętli:

Pętla zewnętrzna nr 1 wybiera ze zbioru element leżący przed listą uporządkowaną.
Pętla wewnętrzna nr 2 poszukuje miejsca wstawienia wybranego elementu na liście uporządkowanej wykorzystując algorytm wyszukiwania binarnego.
Pętla wewnętrzna nr 3 przesuwa elementy listy, aby zrobić miejsce dla elementu wybranego.

Na początku algorytmu inicjujemy licznik j pętli zewnętrznej nr 1. Będzie ona przebiegała przez kolejne indeksy elementów sortowanego zbioru od n - 1 do 1. Na początku tej pętli umieszczamy w zmiennej pomocniczej x element wybrany. Element ten znajduje się tuż przed listą uporządkowaną, która tworzona jest na końcu zbioru. Dalej ustawiamy dwa graniczne indeksy i_p i i_k, które definiują pozycję elementów na liście uporządkowanej. Zwróć uwagę, iż faktycznie indeks i_p wskazuje pozycję przed listą, a i_k wskazuje pozycję za listą. Jest to potrzebne po to, aby pętla warunkowa nr 2 wykonała się przynajmniej jeden raz.

Rozpoczyna się pętla warunkowa nr 2. Jest to typowa pętla while, w której warunek kontynuacji sprawdzamy na początku. Pętla kontynuuje się dopóki partycja listy uporządkowanej zdefiniowana indeksami i_p i i_k zawiera więcej niż 1 element, gdyż tylko wtedy można dokonać podziału na dwie mniejsze partycje. Gdy pętla ta się zakończy, zmienna i_p zawiera indeks pozycji wstawiania na listę uporządkowaną elementu wybranego, przechowywanego w zmiennej pomocniczej x.

Na początku pętli nr 2 wyznaczamy indeks elementu środkowego partycji i umieszczamy go w zmiennej i. Następnie sprawdzamy, czy element wybrany, przechowywany w zmiennej x, jest mniejszy lub równy (dla porządku malejącego większy lub równy) elementowi środkowemu partycji listy uporządkowanej. Jeśli tak, to pozycja wstawiania znajduje się w pierwszej części partycji - wśród elementów o indeksach od i_p do i. W przeciwnym razie za nową partycję przyjmujemy drugą część - elementy o indeksach od i do i_k. Pętlę kontynuujemy do momentu, aż partycja będzie zawierała tylko jeden element. Wtedy nie ma już wątpliwości i pozycja wstawiania zawsze jest w zmiennej i_p.

Po znalezieniu tej pozycji uruchamia się pętla nr 3. Jej zadaniem jest przesunięcie o 1 pozycję w kierunku początku zbioru wszystkich elementów listy uporządkowanej poczynając od jej początku aż do pozycji i_p. Dzięki tej operacji pozycja i_p zostanie zwolniona i umieszczamy na niej element wybrany. Następnie zmniejszamy indeks j i kontynuujemy pętlę zewnętrzną aż do posortowania całego zbioru.

Przykład:

Aby lepiej zrozumieć zasadę działania naszego algorytmu, przeanalizujmy prosty przykład wstawiania elementu na listę uporządkowaną przy pomocy binarnego wyszukiwania pozycji wstawiania. Zbiór ma postać następującą: { 6 3 4 5 7 8 }. Wstawiamy pierwszy element - liczbę 6. Pozostałe elementy tworzą listę uporządkowaną. Na dole szarymi cyferkami podajemy indeksy elementów:

Zbiór	Opis operacji
6 3 4 5 7 8 1 2 3 4 5 6	Ze zbioru wybieramy element. Ustalamy indeksy partycji: ip = 1, ik = 7
6 3 4 5 7 8 1 2 3 4 5 6	Wyznaczamy element środkowy: i = (ip + ik) / 2 = (1 + 7) / 2 = 8 / 2 = 4
6 3 4 5 7 8 1 2 3 4 5 6	Sprawdzamy, czy 6 jest mniejsze lub równe 5. Nie jest, zatem za nową partycję przyjmujemy: ip = i = 4, ik - pozostaje bez zmian, czyli ik = 7
6 3 4 5 7 8 1 2 3 4 5 6	Wyznaczamy nowy element środkowy (pamiętaj, że dzielenie jest całkowitoliczbowe): i = (ip + ik) / 2 = (4 + 7) / 2 = 11 / 2 = 5
6 3 4 5 7 8 1 2 3 4 5 6	Sprawdzamy, czy 6 jest mniejsze lub równe 7. Jest, zatem za nową partycję przyjmujemy: ik = i = 5, ip - pozostaje bez zmian, czyli ip = 4
6 3 4 5 7 8 1 2 3 4 5 6	Ponieważ różnica ik - ip jest już równa 1, zatem ip zawiera numer pozycji wstawienia elementu. Jest to pozycja nr 4 zajmowana obecnie przez liczbę 5.
6 3 4 5 7 8 1 2 3 4 5 6	Przesuwamy o jedną pozycję w kierunku początku zbioru elementy listy od jej początku do pozycji wstawiania.
3 4 5 6 7 8 1 2 3 4 5 6	Element wybrany wstawiamy na zwolnione miejsce. Operacja zakończona

do podrozdziału do strony

C++

// Binarne 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,ip,ik,x;
  
  cout << " Binarne 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];
    ip = j;
    ik = N;
    while(ik - ip > 1)
    {
      i = (ip + ik) / 2;
      if(x <= d[i]) ik = i; else ip = i;
    }
    for(i = j; i < ip; i++) d[i] = d[i + 1];
    d[ip] = 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;
}

Pascal

// Binarne 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,ip,ik : integer;
begin
  writeln(' Binarne 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];
    ip := j;
    ik := N + 1;
    while ik - ip > 1 do
    begin
      i := (ip + ik) div 2;
      if x <= d[i] then ik := i else ip := i;
    end;
    for i := j to ip - 1 do d[i] := d[i + 1];
    d[ip] := 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.

Basic

' Binarne 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
  DIM ip AS INTEGER, ik AS INTEGER

  PRINT " Binarne 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): ip = j: ik = N + 1
    WHILE ik - ip > 1
      i = INT((ip + ik) / 2)
      IF x < d(i) THEN ik = i ELSE ip = i
    WEND
    FOR i = j TO ip - 1: d(i) = d(i + 1): NEXT
    d(ip) = 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="frmbinaryinsertionsort">
      <h3 style="text-align: center">Binarne 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>

// Binarne 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,ip,ik,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];
    ip = j;
    ik = N;
    while(ik - ip > 1)
    {
      i = Math.floor((ip + ik) / 2);
      if(x <= d[i]) ik = i; else ip = i;
    }
    for(i = j; i < ip; i++) d[i] = d[i + 1];
    d[ip] = 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>

Wynik:

Binarne sortowanie przez wstawianie
-------------------------------------
       (C)2005 Jerzy Walaszek

Przed sortowaniem:

30 36 81 45 71 90 15 57 68 24 39 83 54   1 29 48 69 23   0 77

Po sortowaniu:

   0   1 15 23 24 29 30 36 39 45 48 54 57 68 69 71 77 81 83 90

do podrozdziału do strony

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

Pascal

// 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 = 'Binarne 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,ip,ik : integer;
  x         : real;
begin
  QueryPerformanceCounter(addr(qpc1));
  for j := n - 1 downto 1 do
  begin
    x := d[j];
    ip := j;
    ik := n + 1;
    while ik - ip > 1 do
    begin
      i := (ik + ip) div 2;
      if x <= d[i] then ik := i else ip := i;
    end;
    for i := j to ip - 1 do d[i] := d[i + 1];
    d[ip] := 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: Binarne sortowanie przez wstawianie
------------------------------------------------------------------
(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
   1000    0.000179    0.005513    0.000184    0.000197    0.003232
   2000    0.000453    0.023159    0.000381    0.000385    0.013100
   4000    0.000850    0.093319    0.000840    0.000859    0.049430
   8000    0.001854    0.370242    0.001848    0.001816    0.186800
  16000    0.004150    1.480928    0.004025    0.003942    0.740566
  32000    0.008321    6.258433    0.008564    0.008401    3.063959
-------------------------------------------------------------------
Koniec

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

n	-	ilość elementów w sortowanym zbiorze
t_po	-	czas sortowania zbioru posortowanego
t_od	-	czas sortowania zbioru posortowanego malejąco
t_pp	-	czas sortowania zbioru posortowanego z losowym elementem na początku
t_pk	-	czas sortowania zbioru posortowanego z losowym elementem na końcu
t_np	-	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)

do podrozdziału do strony

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

Cechy Algorytmu Binarnego Sortowania Przez Wstawianie
klasa złożoności obliczeniowej optymistyczna
klasa złożoności obliczeniowej typowa
klasa złożoności obliczeniowej pesymistyczna
Sortowanie w miejscu	TAK
Stabilność	TAK

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

optymistyczna - dla zbiorów uporządkowanych (z niewielką liczbą elementów nie na swoich miejscach) - na podstawie czasów t_po, t_pp, t_pk
typowa - dla zbiorów o losowym rozkładzie elementów - na podstawie czasu t_np
pesymistyczna - dla zbiorów posortowanych odwrotnie - na podstawie czasu t_od.

Własności algorytmu
Algorytm	t_po	t_od	t_pp	t_pk	t_np
Binarne sortowanie przez wstawianie
Binarne sortowanie przez wstawianie

Góra zrodziła mysz. Algorytm w wersji zoptymalizowanej posiada gorsze własności od wersji podstawowej. Zwróć uwagę, iż jedyna różnica w klasach złożoności obliczeniowej zachodzi dla przypadku optymistycznego i to na niekorzyść. Teraz mamy złożoność liniowo-logarytmiczną, która jest gorsza od złożoności liniowej w poprzedniej wersji algorytmu. Wynika z tego prosty wniosek - nie opłaca się stosować algorytmu binarnego sortowania przez wstawianie. Ewentualne korzyści są marnowane przez czas zużyty na wykonanie dodatkowych operacji. Wersja podstawowa jest lepsza i szybsza. Być może zysk wystąpiłby przy sortowaniu zbiorów o bardzo dużej liczbie elementów (wtedy oszczędności na operacjach porównań zaczęłyby odgrywać istotną rolę w ogólnym czasie sortowania), jednakże w takich przypadkach lepiej zastosować algorytm sortujący klasy O(n logn), np. Sortowanie Szybkie.

Wzrost prędkości sortowania
Algorytmy	t_po	t_od	t_pp	t_pk	t_np
Sortowanie przez wstawianie Binarne sortowanie przez wstawianie
	źle	źle	źle	źle	źle

Wszystkie parametry nowego algorytmu są gorsze od wersji podstawowej. Być może wersja ta okazałaby się szybsza w sytuacji, gdy operacje porównania pochłaniają dużo więcej czasu w porównaniu z operacjami przesuwania elementów - na przykład przy sortowaniu tablicy łańcuchów znakowych. Proponuję sprawdzenie tej hipotezy ambitnym czytelnikom serwisu.

do podrozdziału do strony

Dlaczego zastosowanie wyszukiwania binarnego daje gorsze wyniki w algorytmie sortowania przez wstawianie? Na jakich operacjach oszczędzamy, a na jakich nie?

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Binarne sortowanie przez wstawianie
Binary Insertion Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Binarne Sortowanie przez Wstawianie

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Binarne sortowanie przez wstawianie Binary Insertion Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Binarne Sortowanie przez Wstawianie

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Binarne sortowanie przez wstawianie
Binary Insertion Sort