Binarne sortowanie przez wstawianie
           Binary Insertion Sort


Podrozdziały     Tematy pokrewne

Algorytm

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

1. 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.

2. 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.

3. 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(log n), 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.

 

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
ip, ik - początkowa i końcowa pozycja indeksów w partycji listy uporządkowanej,   ip, ik N
x - zawiera wybrany ze zbioru element

 

Lista kroków

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

 

Schemat blokowy

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 ip i ik, które definiują pozycję elementów na liście uporządkowanej. Zwróć uwagę, iż faktycznie indeks ip wskazuje pozycję przed listą, a ik 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 ip i ik 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 ip 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 ip do i. W przeciwnym razie za nową partycję przyjmujemy drugą część - elementy o indeksach od i do ik. 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 ip.

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 ip. Dzięki tej operacji pozycja ip 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

    3  4  5  7  8 
 1  2  3  4  5  6 
Ze zbioru wybieramy element. Ustalamy indeksy partycji:
ip = 1, ik = 7

    3  4  5  7  8 
 1  2  3  4  5
Wyznaczamy element środkowy:
i = (ip + ik) / 2 = (1 + 7) / 2 = 8 / 2 = 4
         
    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
         
    3  4  5  7  8 
 1  2  3  4  5
Wyznaczamy nowy element środkowy (pamiętaj, że dzielenie jest całkowitoliczbowe):
i = (ip + ik) / 2 = (4 + 7) / 2 = 11 / 2 = 5
            
    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
            
    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.
            
 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

 

Programy

Efekt uruchomienia programu
 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

 

DevPascal
// 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.
Code::Blocks
// 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;
}
Free 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>

 

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

Binarne 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 binarnego 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 = '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
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 binarnego sortowania przez wstawianie wyciągamy następujące wnioski:

 

Cechy Algorytmu
Binarnego Sortowania Przez Wstawianie
klasa złożoności obliczeniowej optymistyczna O(n log 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
Binarne sortowanie przez wstawianie O(n log n) O(n2) O(n log n) O(n log n) O(n2)
tpo << tod tpp tpk
tnp   1 tod
2
  1. 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 log n), np. Sortowanie Szybkie.
Wzrost prędkości sortowania
Algorytmy tpo tod tpp tpk tnp

Sortowanie przez wstawianie

Binarne sortowanie przez wstawianie

  7
3log2n
  4
5
  8
3log2n
  3
log2n
  4
5
źle źle źle źle źle
  1. 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.

Zadania dla ambitnych

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

Zobacz również na: wersję podstawową

 



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.