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

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

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 << 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 << endl;
  system("pause");
  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;
  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;
  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
  
CONST N = 20 ' Liczebność zbioru.

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

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
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
    END IF
  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
PRINT "Nacisnij Enter..."
SLEEP
END

Python (dodatek)

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

n = 20 # Liczebność zbioru.

d = [random.randrange(100) for i in range(n)]

print(" Binarne sortowanie przez wstawianie ")
print("-------------------------------------")
print("       (C)2026  Jerzy Wałaszek       ")
print()

# wyświetlamy d[]

print("Przed sortowaniem:")
print()
for i in range(n):
    print("%4d" % (d[i]),end="")
print()
print()

# Sortujemy

for j in reversed(range(n)):
    x = d[j]
    ip = j
    ik = n
    while ik - ip > 1:
        i = int((ip + ik) / 2)
        if x < d[i]:
            ik = i
        else:
            ip = i
    for i in range(j,ip):
        d[i] = d[i + 1]
    d[ip] = x

# Wyświetlamy wynik sortowania

print("Po sortowaniu:")
print()
for i in range(n):
    print("%4d" % (d[i]),end="")
print()
print()
input("Naciśnij Enter...")

Wynik:

 Binarne sortowanie przez wstawianie 
-------------------------------------
       (C)2026  Jerzy Wałaszek       

Przed sortowaniem:

  83  63  17  36  75  84  28  43  12  91  92  21  84  96   7   8  54  19  85  20

Po sortowaniu:

   7   8  12  17  19  20  21  28  36  43  54  63  75  83  84  84  85  91  92  96

Naciśnij Enter...

JavaScript

<html>
  <head>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align:
               center;
               background-color:
               #E7E7DA">
          <b>&nbsp;&nbsp;
          Binarne Sortowanie
          Przez Wstawianie
          &nbsp;&nbsp;</b><br/>
          (C)2026 mgr
          Jerzy Wałaszek
          &nbsp;&nbsp;<hr/>
          <input
          onclick="main()"
          value="Sortuj"
          name="B1"
          type="button">
          <hr/>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script language="javascript">

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

var N = 20;

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("out")
  .innerHTML = t;
}

</script>

  </body>
</html>

do podrozdziału do strony

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

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

Podsumowanie

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

Podsumowanie

Binarne sortowanie przez wstawianie
Binary Insertion Sort