Sortowanie przez wstawianie z wyszukiwaniem binarnym

Rozważmy jeszcze raz algorytm sortowania przez wstawianie. W tym algorytmie jedna faza polega głównie na umiejscowieniu wstawianego elementu w uporządkowanym ciągu - w fazie \( i \)-tej element \( a[i] \) wstawiamy do uporządkowanego ciągu \( a[1..i-1] \), dla \( i = 2,3, \ldots, n \). Miejsce, w które należy wstawić element \( a[i] \), można znaleźć za pomocą wyszukiwania binarnego.

Algorytm Sortowanie przez wstawianie z wyszukiwaniem binarnym

InsertionSortWithBinarySearch 
  for i := 2 to n do 
  begin
    //a[1..i-1] jest już posortowana 
    x := a[i]  //odkładamy element z pozycji i 
    //binarne wyszukiwanie największego  j <= i  takiego, że a[j-1] <= x  
    l := 0; p := i; 
    while (p - l) > 1 do 
    //Niezmiennik: a[l] <= x oraz x <  a[p] jeśli tylko p  <  i 
    begin 
      s := (l+p) div 2; 
      if x  <  a[s] then 
        p := s;  
      else 
        l := s;
    end 
    j := l+1;
    //x zostanie wstawiony na pozycję j; 
    //elementy większe przesuwamy o 1 pozycję w prawo 
    for k := i downto j+1 do 
      a[k] := a[k-1];  
    a[j] := x  
 end;

W tym algorytmie liczbę wykonywanych porównań można wyznaczyć następująco: w iteracji o numerze \( i \) zewnętrznej pętli for wykonuje się co najwyżej \( \lceil \log i \rceil \) porównań pomiędzy elementami sortowanego ciągu, co w sumie daje

\( \sum_{i = 2} \lceil \log i \rceil = n\lceil \log n \rceil - 2^{\lceil \log n \rceil} + 1 \)

porównań.

Otrzymaliśmy więc algorytm, w którym wykonuje się \( O(n\log n) \) porównań niezbędnych do wyszukiwania miejsc dla wstawianych elementów, ale (niestety) liczba przesunięć elementów w tablicy, koniecznych do zrobienia tych miejsc, jest w pesymistycznym przypadku kwadratowa. Ta obserwacja jest niezwykle pouczająca. Mówi ona, że dobór operacji dominujących dla analizy złożoności algorytmu jest kluczowy dla jakości tej analizy.

Sortowanie przez wstawianie z wyszukiwaniem binarnym jest też warte wspomnienia dlatego, że jego pomysłodawcą był wybitny polski matematyk Hugo Steinhaus. O tej metodzie sortowania Steinhaus wspomina w drugim wydaniu swojej znakomitej książki Kalejdoskop matematyczny z roku 1950.

Informatyka MIMUW

Sortowanie przez wstawianie z wyszukiwaniem binarnym