Analiza sortowania przez wstawianie

Podobnie jak sortowanie przez wybieranie, sortowanie przez wstawianie wykonuje pętle powtórzeń na indeksach tablicy. Wywołuje funkcję insert na elementach o indeksach $1,2,3,\dots ,n-1$‍. Podobnie jak każde wywołanie funkcji indexOfMinimum zajmuje jakiś czas, zależny od rozmiaru posortowanej podtablicy, tak też dzieje się z każdym wywołaniem funkcji insert. Właściwie, słowo "dzieje się" w poprzednim zdaniu powinno być zastąpione wyrażeniem "może się dziać" i zaraz przekonamy się dlaczego.

Rozważmy najpierw sytuację, w której wywołujemy funkcję insert a wartość elementu, który chcemy wstawić do podtablicy jest mniejsza niż każdy element w tej podtablicy. Na przykład: gdy wstawiamy 0 do podtablicy [2, 3, 5, 7, 11], wtedy każdy element podtablicy musi zostać przesunięty o jedną pozycję w prawo. Ogólnie rzecz biorąc, jeśli wstawiamy do podtablicy z $k$‍ elementami, może mieć miejsce taka sytuacja, że wszystkie $k$‍ będą musiały być przesunięte o jedną pozycję. Zamiast liczyć dokładnie ile linijek kodu potrzebujemy, aby porównać element znajdujący się przed kluczem i przesunąć go, przyjmijmy, że jest to stała liczba linii; niech to będzie stała $c$‍. Dlatego nawet do $c\cdot k$‍ linii może zająć sytuacja wstawiania wartości do podtablicy $k$‍-elementowej.

Załóżmy, że przy każdym wywołaniu insert wartość wstawiana jest mniejsza od wszystkich elementów w części tablicy na lewo od wartości wstawianej. Za pierwszym wywołaniem insert $k=1$‍. Za drugim razem $k=2$‍. Za trzecim $k=3$‍ i tak dalej aż do końca, gdy $k=n-1$‍. Zatem całkowity czas spędzony na wstawianiu do posortowanej podtablicy wynosi

$c\cdot 1+c\cdot 2+c\cdot 3+\cdots c\cdot (n-1)=c\cdot (1+2+3+\cdots +(n-1))$‍ .

To jest suma ciągu arytmetycznego rosnącego do wartości $n-1$‍ (zazwyczaj spotyka się notację do $n$‍). Korzystając ze wzoru na sumę ciągu arytmetycznego, otrzymujemy całkowity czas spędzony na wstawianiu do posortowanej podtablicy

$c\cdot (n-1+1)((n-1)/2)=c{n}^2/2-cn/2$‍ .

W notacji Θ zaniedbujemy wyrazy o niższych rzędach - tutaj $cn/2$‍ - i współczynniki stałe - tutaj $c$‍ i 1/2. Otrzymujemy w wyniku oszacowanie czasu pracy sortowania przez wstawianie, w rozpatrywanym przykładzie, $\mathrm{\Theta }(n^2)$‍.

Czy sortowanie przez wstawianie może zająć mniej czasu niż $\mathrm{\Theta }(n^2)$‍? Odpowiedź brzmi: tak. Załóżmy, że mamy tablicę [2, 3, 5, 7, 11], w której posortowaną podtablicę stanowią pierwsze cztery elementy, a my wstawiamy do niej wartość 11. Już w pierwszym sprawdzeniu widzimy, że wartość 11 jest większa od 7, a co za tym idzie, żaden element podtablicy nie będzie musiał być przesunięty w prawo. Wtedy wywołanie funkcji insert zajmuje po prostu stałą ilość czasu. Załóżmy, że każde wywołanie funkcji insert zajmuje stałą ilość czasu. Ze względu na to, że mamy $n-1$‍ wywołań funkcji insert, jeśli każde wywołanie zajmuje stałą ilość czasu $c$‍, wtedy całkowity czas sortowania przez wstawianie wynosi $c\cdot (n-1)$‍, co z kolei wynosi $\mathrm{\Theta }(n)$‍, a nie $\mathrm{\Theta }(n^2)$‍.

Czy może się zdarzyć, że żadna z powyższych sytuacji nie będzie miała miejsca? Czy każde wywołanie funkcji insert może powodować, że każdy element w podtablicy będzie musiał być przesunięty o jedną pozycję w prawo? Czy każde wywołanie funkcji insert może nie wymagać przesuwania elementów? Odpowiedź brzmi: tak. Wywołanie funkcji insert powoduje, że każdy element jest przesuwany, jeśli wstawiany klucz jest mniejszy niż każdy element po jego lewej stronie. Zatem jeśli każdy element jest większy lub równy swoim sąsiadom po lewej stronie, czas sortowania przez wstawianie wynosi $\mathrm{\Theta }(n)$‍. Co to oznacza, że każdy element jest mniejszy od swojego sąsiada po lewej stronie? To znaczy, że tablica jest posortowana w odwrotnej kolejności np. [11, 7, 5, 3, 2]. Zatem przypadek odwrotnie posortowanej tablicy jest najgorszym przypadkiem dla sortowania przez wstawianie.

Co z przeciwnym przypadkiem? Wywołanie funkcji insert powoduje, że nie ma elementów do przesuwania jeśli klucz, który chcemy wstawić jest większy lub równy każdemu elementowi po swojej lewej stronie. Zatem jeśli każdy element jest większy lub równy swoim sąsiadom po lewej stronie, czas sortowania przez wstawianie wynosi $\mathrm{\Theta }(n)$‍. Taka sytuacja ma miejsce, gdy tablica, do której wstawiamy element, jest już posortowana, zatem tablica posortowana to najlepszy przypadek dla sortowania przez wstawianie.

Co jeszcze możemy powiedzieć o czasie wykonywania sortowania przez wstawianie? Załóżmy, że elementy tablicy ułożone są w losowym porządku. W takim przypadku, uśredniając, oczekujemy, że każdy element jest mniejszy niż połowa elementów z jego lewej strony. Wówczas wywołanie funkcji insert na $k$‍-elementowej podtablicy spowoduje przesunięcie średnio $k/2$‍ elementów. Czas wykonania wynosi wtedy połowę czasu potrzebnego dla najgorszego przypadku. Jednak w notacji asymptotycznej, gdzie stałe współczynniki nie mają znaczenia, czasu wykonania sortowania w średnim przypadku wciąż wynosi $\mathrm{\Theta }(n^2)$‍ - tak jak w najgorszym przypadku.

A co gdybyśmy wiedzieli, że tablica jest "prawie posortowana"? Każdy element na początku jest w pewnej stałej odległości (np. 17) od pozycji, w której będzie się znajdował po wykonaniu sortowania? Wówczas każde wywołanie funkcji insert powodowałoby przesunięcie co najwyżej 17 elementów a czas wykonania jednej funkcji insert na $k$‍-elementowej podtablicy wynosiłby co najwyżej $17\cdot c$‍. Biorąc pod uwagę $n-1$‍ wywołań funkcji insert, czas wykonania wynosi $17\cdot c\cdot (n-1)$‍, co oznacza $\mathrm{\Theta }(n)$‍ - tak jak w najlepszym przypadku. Zatem sortowanie przez wstawianie jest szybkie, gdy mamy "prawie posortowaną" tablicę.

Podsumowując, czas wykonania dla sortowania przez wstawianie wynosi:

Jeśli musielibyśmy uogólnić stwierdzenie na wszystkie przypadki sortowania przez wstawianie, powiedzielibyśmy, że wykonuje się ono w czasie $O(n^2)$‍. Nie można powiedzieć, że przebiega ono w czasie $\mathrm{\Theta }(n^2)$‍ dla wszystkich przypadków, skoro najlepszy przypadek przebiega w czasie $\mathrm{\Theta }(n)$‍. I jednocześnie nie można powiedzieć, że przebiega ono w czasie $\mathrm{\Theta }(n)$‍ we wszystkich przypadkach, skoro w najgorszym przypadku czas wykonania wynosi $\mathrm{\Theta }(n^2)$‍.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.