Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 1
Lekcja 5: Sortowanie przez wstawianieAnaliza sortowania przez wstawianie
Podobnie jak sortowanie przez wybieranie, sortowanie przez wstawianie wykonuje pętle powtórzeń na indeksach tablicy. Wywołuje funkcję . Podobnie jak każde wywołanie funkcji
insert
na elementach o indeksach 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ę elementami, może mieć miejsce taka sytuacja, że wszystkie 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 . Dlatego nawet do linii może zająć sytuacja wstawiania wartości do podtablicy -elementowej.
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 Załóżmy, że przy każdym wywołaniu . Za drugim razem . Za trzecim i tak dalej aż do końca, gdy . Zatem całkowity czas spędzony na wstawianiu do posortowanej podtablicy wynosi
insert
wartość wstawiana jest mniejsza od wszystkich elementów w części tablicy na lewo od wartości wstawianej. Za pierwszym wywołaniem insert
To jest suma ciągu arytmetycznego rosnącego do wartości (zazwyczaj spotyka się notację do ). Korzystając ze wzoru na sumę ciągu arytmetycznego, otrzymujemy całkowity czas spędzony na wstawianiu do posortowanej podtablicy
W notacji Θ zaniedbujemy wyrazy o niższych rzędach - tutaj - i współczynniki stałe - tutaj i 1/2. Otrzymujemy w wyniku oszacowanie czasu pracy sortowania przez wstawianie, w rozpatrywanym przykładzie, .
Czy sortowanie przez wstawianie może zająć mniej czasu niż ? 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 wywołań funkcji , wtedy całkowity czas sortowania przez wstawianie wynosi , co z kolei wynosi , a nie .
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 insert
, jeśli każde wywołanie zajmuje stałą ilość czasu Czy może się zdarzyć, że żadna z powyższych sytuacji nie będzie miała miejsca? Czy każde wywołanie funkcji . 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.
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 Co z przeciwnym przypadkiem? Wywołanie funkcji . Taka sytuacja ma miejsce, gdy tablica, do której wstawiamy element, jest już posortowana, zatem tablica posortowana to najlepszy przypadek dla sortowania przez wstawianie.
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 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 -elementowej podtablicy spowoduje przesunięcie średnio 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 - tak jak w najgorszym przypadku.
insert
na 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 -elementowej podtablicy wynosiłby co najwyżej . Biorąc pod uwagę wywołań funkcji , co oznacza - tak jak w najlepszym przypadku. Zatem sortowanie przez wstawianie jest szybkie, gdy mamy "prawie posortowaną" tablicę.
insert
powodowałoby przesunięcie co najwyżej 17 elementów a czas wykonania jednej funkcji insert
na insert
, czas wykonania wynosi Podsumowując, czas wykonania dla sortowania przez wstawianie wynosi:
- W najgorszym przypadku:
. - W najlepszym przypadku:
. - Średnia w przypadku tablicy losowej
. - W "prawie posortowanym" przypadku:
.
Jeśli musielibyśmy uogólnić stwierdzenie na wszystkie przypadki sortowania przez wstawianie, powiedzielibyśmy, że wykonuje się ono w czasie . Nie można powiedzieć, że przebiega ono w czasie dla wszystkich przypadków, skoro najlepszy przypadek przebiega w czasie . I jednocześnie nie można powiedzieć, że przebiega ono w czasie we wszystkich przypadkach, skoro w najgorszym przypadku czas wykonania wynosi .
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.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji