Problem sortowania
Sortowanie jest to dokładnie to co myślisz, że to jest. Jest to problem ułożenia jakiejś struktury danych, którą da się uporządkować, wedle jakiegoś porządku. Może to być dowolna struktura, która jak wspomniałem, musi mieć możliwość uporządkowania, tj. np. nie może to być zbiór, ale może to być lista bądź tablica. Wedle jakiegoś porządku, to znaczy, wedle porządku który pasuje do danych, które się w tej strukturze znajdują i pasuje do algorytmu który sobie wybierzemy. Sam algorytm też, musi pasować do naszej struktury danych. Dużo dopasowywania. Rozbijmy więc to sobie na czynniki pierwsze i zobaczmy, z czego owo dopasowywanie wynika i jak je odpowiednio dobrać.
Definicja formalna
Formalnie rzecz ujmując sortowanie jest to proces ustalenia permutacji danego ciągu danych, która spełnia warunek ustalonego wcześniej porządku porządku \(P\) (Czym jest porządek można zobaczyć tu). Jaki ten porządek musi być, zależy już od tego jakiego algorytmu używamy, niemniej zazwyczaj będzie to porządek zupełny, jako że rzadko w praktyce mamy do czynienia z innymi. Może to być np. \(e_1 \leq e_2 \leq\space ... \leq e_n\) lub \(e_1 \gt e_2 \gt\space ... \gt e_n\), gdzie \(e_i\) oznacza element o indeksie \(i\) w danej permutacji ciągu, lub dowolne porównanie jakie sobie wymyślimy dla naszych danych wejściowych. Można to sobie zapisać tak:
\(s(c_{we}) = c_{wy}, \text{gdzie } c_{wy} \text{ podlega } P\)
Gdzie \(s\) będzie funkcją sortowania, \(c_{we}\) ciągiem wejściowym, \(c_{wy}\) ciągiem wyjściowym, a \(P\) ustalonym porządkiem.
Istnieją dwa rodzaje sortowania, a ich wybór zależy od tego z jakimi danymi mamy do czynienia. Zaczniemy od przypadku ogólnego, czyli takiego, który będzie "działać" dla dowolnego rodzaju danych, bez żadnych wymogów innych niż możliwośc porównania.
Sortowanie porównawcze
Wydawać by się mogło, że jest to jedyna forma, której można by użyć by nadać jakiemuś ciągowi pożądaną kolejność. Jednakże tak nie jest. Opiszemy ją jednak jako pierwszą, ponieważ jest dosyć "naturalna" i zdecydowanie bardziej często spotykana w normalnym użytkowaniu.
Definicja formalna
Wróćmy do podstawowej definicji, lekko ją modyfikując. Nadal będzie to proces ustalenia permutacji danego ciągu danych, wedle jakiegoś porządku (oczywiście ta definicja wystarczy w zupełności, jednak chciałbym ją rozszerzyć, żeby ją trochę "upraktycznić"). Wprowadzimy tym samym pojęcia funkcji porównania albo komparatora. Komparator będzie funkcją \(f(e_0, e_1)\), która zwróci nam w zależności od tego co potrzebujemy stosunek porównania argumentów \(e_0\) i \(e_1\), czyli powie czy owe elementy są sobie równe, czy \(e_0\) jest mniejsze od \(e_1\) itd. Czemu mówię o tym, że zwróci nam to czego potrzebujemy, a nie wszystkie wartości, czyli większy, mniejszy, równy? Ano dlatego, że czasami można sobie takie rzeczy wydedukować. Weźmy ciąg liczbowy, w którym sortujemy rosnąco. Musimy wiedzieć tylko, czy element jest większy od innego, bo jeżeli nie jest, to jest mniejszy lub równy, i nie musimy go przestawiać. Można też np. sprawdzić mniejszość, później większość, i gdy oba te sprawdzenia dadzą wynik negatywny, oznaczać będzie to, że oba porównywane elementy są sobie równe. Nie jest to przypadek ogólny, bo operacje porównania można definiować dowolnie i porządki mogą być dowolne, ale na przykładzie liczb bardzo dobrze widać to co chciałem pokazać, czyli dedukcję i zbyteczność niektórych operacji w niektórych przypadkach. Problem dowolnego porządku nie będzie dla nas raczej problemem. Problem sortowania porównawczego zawęża się do elementów, które da się w trywialny sposób porównać, albo wymusza się sprowadzenie skomplikowanych struktur danych do tych, które trywialnie da się porównać, lub ustalić zupełny porządek. Czyni się to właśnie komparatorami, bo użytkownik musi wiedzieć co sortuje i w jaki sposób będzie to sortować. My jako projektanci algorytmu dostarczymy rozwiązanie, które posortuje coś trywialnie porównywalnego w dobrym czasie, a zadaniem użytkownika będzie już dostosowanie się do nas.
W literaturze można spotkać się z pojęciem rekordu i klucza rekordu. Rekord będzie tym, co my nazwaliśmy daną, albo elementem. Czyli jakiś abstrakt nad naszymi danymi. Kluczem rekordu nazwiemy to co my określiliśmy czymś trywialnie porównywalnym, czyli jakąś cechą rekordu, danej, która będzie nam go identyfikować, i wedle którego będziemy sortować, czyli ten klucz właśnie będziemy porównywać z innymi kluczami innych rekordów.
Nieformalnie mamy jakiś ciąg, wymyślamy sobie jak porównać elementy tego ciągu (np. większe, mniejsze, jak są to słowa, to np. alfabetycznie, albo ilością liter), żeby dało się je sklasyfikować jako mniejsze lub większe, lub równe i ustawiamy te elementy wedle tego co ustaliliśmy. Zadanie z pozoru łatwe, jednakże zobaczysz, że nie jest tak w praktyce, gdy mowa o deterministycznej automatyzacji takiego procesu, który ma działać szybko i zawsze poprawnie.
Mając w głowie to co mamy, możemy stworzyć definicję operacji sortowania porównawczego. Będzie to funkcja, która będzie przyjmowała dwa parametry: ciąg wejściowy oraz funkcję porównania/komparator. Jej wynikiem będzie ciąg wyjściowy, którego elementy będą odpowiadać temu wejściowemu, tylko w innej kolejności. A więc:
\(s(c_{we}, k) = c_{wy}\)
Gdzie \(s\) jest funkcją sortowania, \(c_{we}\) ciągiem wejściowym, \(k\) komparatorem, a \(c_{wy}\) ciągiem wyjściowym.
Sortowanie bez porównań
Ten rodzaj wziął się raczej z badań nad samym procesem sortowania i szukania najlepszego rozwiązania dla konkretnego typu danych mającego konkretne cechy. Wykorzystywać tu będziemy konkretne cechy danych, by w zręczny sposób doprowadzić do ich posortowania. Jakie to będą cechy i jakie będą im stawiane wymagania, to zależy już od konkretnego algorytmu. Przykładem będzie np. sortowanie przez zliczanie, którego wymaganiem jest, że klucz naszej danej da się sprowadzić do niezerowej liczby całkowitej, która jest mniejsza niż rozmiar ciągu wejściowego.
Czemu taki pomysł powstał? Otóż dlatego, że pozwala on nam przekroczyć granicę nieosiągalną dla algorytmów używających porównań, czyli mieć złożoność czasową mniejszą niż \(\Omega(n\cdot\log{n})\). Skąd to ograniczenie, to później. Wszystko po kolei.
Definicja formalna będzie tu dokładnie taka sama jak dla ogólnego problemu sortowania, więc nie będziemy tutaj nic wymyślać.
Sortowanie dla śmiechu
Istnieją jeszcze algorytmy, które nie są stworzone na poważnie, ale również realizują zadania sortowania w różny sposób. Nie będziemy się tutaj nad nimi roztkliwiać, bo nie ma zasadniczo nad czym, ale dla porządku warto wspomnieć, że takowe istnieją. Przykładem może być np. bogosort albo slowsort.
Algorytm i jego cechy
Mając zdefiniowany problem, możemy przejść do jego rozwiązania. Rozwiązaniem problemu sortowania będzie algorytm sortujący. Algorytm owy będzie realizował dokładnie to co określiliśmy wyżej, czyli weźmie jakiś ciąg i go poukłada wedle naszego porządku. Algorytmów sortowania jest wiele i jak każdy inny algorytm będzie się cechował pewnymi właściwościami, które określały będą jego przydatność dla konkretnych rozwiązań, oraz będą stawiały go w szeregu bycia lepszym bądź gorszym ze względu na te kryteria, np. czas. Omówmy więc po kolei każdą z cech jakie będziemy mogli wyszczególnić:
Złożoność obliczeniowa
Problem złożoności obliczeniowej poruszyliśmy już tutaj, nie będę go więc rozwijał, lekko go tylko streszczę. Chodzi o to jak dużo operacji, w relacji do ilości danych wejściowych, będzie musiał algorytm wykonać. Im mniej, tym lepiej. Będziemy więc szukać algorytmów, który tę cechę, tę funkcję, będzie miał jak najniższego rzędu.
Złożoność średnia i najgorszego przypadku
Czyli sprowadzanie naszego algorytmu do tego co robi najgorzej i najczęściej. Jest to dosyć istotne, dlatego, że najgorsza możliwa złożoność nie zawsze będzie tą, która będzie nas interesować z praktycznego punktu widzenia, lub po prostu z braku lepszej alternatywy. Sprawdzimy tutaj jaka będzie złożoność dla najbardziej niekorzystnego dla nas ciągu wejściowego, czyli ile maksimum czasu możemy tu spędzić. Średnia złożoność powie nam, jak średnio długo będziemy czekać na wynik. Dlaczego tak się robi? Z braku lepszej alternatywy właśnie. Przykładem niech będzie sortowanie bąbelkowe które ma taką samą złożoność najgorszego przypadku jak sortowanie szybkie, które szeroko wykorzystuje się na co dzień wszędzie gdzie mowa o sortowaniu. Czemu? Właśnie ze względu na małą częstotliwość występowania najgorszego przypadku. Skąd takie założenie i jak się to liczy, to już temat na inną rozprawę.
Złożoność pamięciowa
Tak samo jak czas, ważne jest dla nas ile pamięci potrzebuje algorytm podczas aplikacji. Będzie to ważne, ponieważ pamięć jest ograniczona, a jest ekstensywne użycie może być niepraktyczne. Mniejsza jej ilość zazwyczaj pozwala też skorzystać z cech urządzeń praktycznych, które mają pewne usprawnienia, które przyspieszają do niej dostęp (np. cache). Będzie więc to też istotna cecha i druga najważniejsza zaraz po czasowej złożoności, która będzie brana pod uwagę podczas porównywania algorytmów. Jeżeli algorytm nie potrzebuje żadnej dodatkowej pamięci, oprócz tej, która podawana mu jest jako ciąg wejściowy, algorytm będzie wtedy sortował w miejscu, czyli bez udziału dodatkowych zasobów.
Rekursywność/Rekurencyjność
Będzie to kryterium, które stwierdzi czy potrzebny jest algorytmowi w jakiś sposób rekurencja. Czemu to jest ważne? Nie jest. Będzie mogło to tylko trochę uprzykrzyć życie implementującemu, ponieważ rekurencji się zazwyczaj unika, ze względu na praktyczne implementacje komputerów, a będzie on musiał ją rozwinąć.
Stabilność
Będzie to kryterium, które powie nam, czy algorytm zostawi w spokoju elementy, które wedle naszego porządku nie będą musiały zmienić kolejności. Znaczy to tyle, że jak w naszym ciągu znajdzie się wiele elementów, którego klucz będzie taki sam, a któreś z nich nie będą musiały być przestawione, ze względu na porządek, ale bądą ze względu na samą specyfikę działania algorytmu, to wtedy algorytm nazwiemy niestabilnym, każdy inny przypadek będzie definiował algorytm stabilny. Czasami może być to istotne, jeżeli chcemy zminimalizować ilość przestawień, ze względu np. na ich kosztowność, albo istotność danych, które są definiowane pod tym kluczem. Np. kolejność na liście wyników konkursu, które poddane niestabilnemu sortowaniu pokażą uczestników z taką samą ilością punktów w różnych kolejnościach. Mówiąc ściślej, musimy zachować względną kolejność elementów o równym kluczu ciągu przed posortowaniem i po sortowaniu.
Możliwość zrównoleglenia
Będzie to kryterium, które powie nam czy nasz algorytm da się rozbić na wiele maszyn/wątków/procesów, które przez zwiększenie ich ilości, może doprowadzić do zmniejszenia czasu przetwarzania. Znaczy to tyle, że jeżeli nasz algorytm da się zrównoleglić, to zamiast wykonywać go na jednym komputerze, można dane rozprowadzić na dwa komputery i zmniejszyć czas sortowania, np. o połowę.
Adaptacyjność
Będzie to kryterium, które powie nam, czy czas wykonania algorytmu, można zmniejszyć, jeżeli ciąg wejściowy jest już częściowo posortowany. Oznacza to tyle, że jeżeli jest, to algorytm musi wykonać znacznie mniej pracy, niż w przypadku, gdyby tak nie było. Nie jest to oczywiste dla wszystkich algorytmów, dlatego jest to istotne, ponieważ np. projektuje się specjalnie wersje algorytmów, które są adaptacyjne, dla algorytmów które takie nie są. Przykładem algorytmu adaptacyjnego jest sortowanie przez wstawianie.
Strumieniowość/Ciagłość
Będzie to kryterium, które powie nam, czy jak będziemy dodawać do ciągu po jednym elemencie i kontynuować proces sortowania, tak jakby doładowując dane, np. z internetu, nie czekając na wszystkie, algorytm będzie w stanie to obsłużyć. Nie jest to możliwe dla wszystkich algorytmów, ponieważ niektóre muszą wiedzieć od początku gdzie są wszystkie elementy i jakiej są wartości. Przykładem algorytmu strumieniowego będzie sortowanie przez wstawianie a antyprzykładem sortowanie szybkie.
Metoda
Można algorytmy sortujące grupować na podstawie tego, jakiego głównie sposobu używają. Przykładami takich sposobów będą: wstawianie, przestawianie, wybieranie, partycjonowanie, spajanie itd. i ich kombinacje.
Porównanie i brak porównań
O tym już powiedziałem, ale wspominam dla porządku.
Inne
Dodatkowo można wymyślić jeszcze wiele innych kryteriów, które będą nam odpowiadać, żeby wybrać lepszy lub gorszy algorytm dla naszego przypadku. Jednym z przykładów może być łatwość implementacji, albo ilość pamięci, którą zajmie kod programu, jeżeli programujemy na urządzenia wbudowane i mamy jest stosunkowo mało. Wybór jest dowolny, także jeżeli spotkasz się z jakimś kryterium, którego tu nie ma, nie bądź zdziwiony.
Problem \(\Omega(n\cdot\log{n})\)
Wspomniałem wcześniej, że istnieje blokada dla algorytmów porównujących, których nie da się zrealizować lepiej niż \(\Omega(n\cdot\log{n})\). Tłumacząc na polski, nie da się zrealizować algorytmu porównującego, który w najgorszym przypadku wykonuje mniej niż \(n\cdot\log{n}\) operacji. Pytanie brzmi dlaczego? Odpowiedzmy na nie.
Algorytm porównujący porównuje. Musi to robić, by wiedzieć, czy aktualne elementy ciągu na którym pracuje, są od siebie mniejsze/większe. Musimy teraz spróbować wywnioskować, jaki jest minimum porównań, które musi on wykonać, mając najgorszą możliwą sytuację, a dla każdego algorytmu może być ona inna. Spróbujemy więc zrealizować jakiś przykład, który obejmie wszystkie możliwe przypadki.
Wiemy na pewno, że wynikiem działania algorytmu sortującego jest permutacja ciągu wejściowego. Algorytm, żeby dać nam ciąg, który na pewno jest posortowany, musi mieć możliwość sprawdzenia wszystkich możliwych permutacji, których jest \(n!\). W jaki sposób to sprawdzi, to już druga sprawa, musi jednak sprawdzić wszystkie. Musi podjąć jakąś ilość kroków, która zależna od ilości elementów wejściowych \(n\), może zostać opisana funkcją \(f(n)\). Skoro ma tylko tyle kroków, może sprawdzić maksymalnie \(2^{f(n)}\) opcji. Dlaczego? Ano dlatego, że mając \(n\) porównań np. możemy podjąć maksymalnie \(n\) decyzji, co daje nam \(2^n\) wygenerowanych opcji. Można to sobie porównać do ciągu bitów i tego, jak pojedynczy bit zawiera informację, czy owy element jest w kolejności, czy nie, w danej permutacji, mając \(n\) bitów. Wiemy więc, że skoro algorytm ma dostęp do naszej permutacji, bo sortuje poprawnie ciąg wejściowy, sprawdzając maksymalnie \(2^{f(n)}\) opcji, a ilość dostępnych opcji to \(n!\), możemy wywnioskować, że \(2^{f(n)} \geq n!\), czyli że w wygenerowanych opcjach, znajduje się więcej, lub tyle samo co rzeczywistych permutacji. Musimy teraz wydostać naszą funkcję, żeby określić jej wartość. Zlogarytmujmy ją więc dwustronnie:
\(log_2{(2^{f(n)})} \geq log_2{(n!)}\)
\(f(n) \geq log_2{(n!)}\)
Co daje nam wniosek, że liczba porównań, potrzebna do znalezienia poprawnej permutacji, czy też zgodnej z naszym porządkiem, MUSI być większa bądź równa \(log_2{(n!)}\) i nie da się tego zrealizować szybciej. Skąd więc funkcja z tytułu tego podrozdziału? Mając wynik \(log_2{(n!)}\) musimy sprowadzić go do funkcji złożoności, a więc \(\Omega(log_2{(n!)})\). Pamiętamy, że funkcja złożoności pokazuje nam rząd wielkości, a tutaj mamy dwa na raz. Musimy więc sprowadzić te funkcję, która pokazuje nam rząd złożoności. Skorzystać możemy z wzoru Sterlinga, który stanowi, że:
\(ln{(n!)} = n\cdot ln{(n)} - n + O(ln{(n)})\)
Gdzie \(ln\) oznacza logarytm naturalny. Wyprowadzenie tego wzoru, to sprawa na osobny artykuł, więc nie będziemy tego tutaj robić. \(O(ln{(n)})\) w tym wzorze, będzie oznaczało, że błąd przybliżenia, bo jest to przybliżenie, będzie maksymalnie \(ln{(n)}\) dla odpowiednio dużych \(n\). Możemy więc ten czynnik pominąć i napisać, że:
\(ln{(n!)} \approx n\cdot ln{(n)} - n\)
Pomijając błąd i uzyskując przybliżenie jakiego potrzebujemy. Możemy teraz dowolnie zmienić podstawę logarytmu, zmieńmy ją więc na \(2\), jako, że taką ma nasz wzór pierwotny:
\(\displaystyle log_2{e} \cdot ln{(n!)} \approx log_2{e} \cdot (ln{(n)} \cdot n - n)\)
Ze wzoru:
\(\displaystyle log_a{b} = \frac{log_c{b}}{log_c{a}}\)
Widzimy, że wymnożenie obu stron zmieni nam podstawę logarytmu. Pomnożenie \(log_2{e}\) i \(ln{(n!)}\), sprawi, że otrzymamy \(log_2{(n!)}\), z prawej podobnie, tylko że z samym \(n\):
\(\displaystyle log_2{n!} \approx log_2{(n)} \cdot n - n \cdot log_2{e}\)
Z własności funkcji złożoności, redukujemy stałe czynniki:
\(\displaystyle \Omega(log_2{n!}) \approx \Omega(log_2{(n)} \cdot n) - \Omega(n \cdot log_2{e})\)
\(\displaystyle \Omega(log_2{n!}) \approx \Omega(log_2{(n)} \cdot n) - \Omega(n)\)
Następnie, również z właśności, sprowadzamy prawą stronę do najwyższego rzędu:
\(\displaystyle \Omega(log_2{n!}) \approx \Omega(log_2{(n)} \cdot n)\)
Co po odwróceniu logarytmu z \(n\)ką, da nam:
\(\displaystyle \Omega(log_2{n!}) = \Omega(n\cdot log_2{(n)})\)
Czyli ten sam wzór co w tytule.
Przykłady
Mając w głowie całą wiedzę, którą tutaj zgromadziliśmy, zrealizujmy sobie dwa przykłady, bardzo proste, bez większego kombinowania. Zaimplementujmy sobie dwa porównujące algorytmy, przeprowadźmy ich analizę i porównajmy je. Spróbujemy swoich sił z sortowaniem bąbelkowym oraz przez wstawianie, wielokrotnie już tutaj przytaczanymi.
Sortowanie bąbelkowe
Pierwszym przykładem i zarazem najprostszym, będzie sortowanie bąbelkowe. Najgorszy z "poważnych" algorytmów, nie mniej działający. Jego koncept jest bardzo prosty. Przechodząc wielokrotnie po całym ciągu wejściowym, "wynosimy", jak bąbelek jest wynoszony przez siłę wyporu, największą znalezioną wartość na sam szczyt (lub najmniejszą, w zależności od komparatora). Mamy więc taki zestaw kroków:
- Porównaj \(1\) element z \(2\)
- Jeżeli \(2\) mniejszy niż \(1\), zamień je miejscami
- Porównaj \(2\) element z \(3\)
- Jeżeli \(3\) mniejszy niż \(2\), zamień je miejscami
- ...
- Porównaj \(n - 1\) element z \(n\)
- jeżeli \(n\) mniejszy niż \(n - 1\), zamień je miejscami
Po takim przejściu, mamy pewność, że największy element naszego ciągu znajduje się na samym końcu naszego ciągu. Teraz jednak musimy zadbać o całą resztę elementów, ale z wiedzą, że ostatni już na pewno jest na odpowiednim miejscu, możemy go pominąć w sprawdzaniu. W następnej iteracji więc, mamy już taki zestaw kroków:
- Porównaj \(1\) element z \(2\)
- Jeżeli \(2\) mniejszy niż \(1\), zamień je miejscami
- Porównaj \(2\) element z \(3\)
- Jeżeli \(3\) mniejszy niż \(2\), zamień je miejscami
- ...
- Porównaj \(n - 2\) element z \(n - 1\)
- jeżeli \(n - 2\) mniejszy niż \(n - 1\), zamień je miejscami
Teraz mamy pewność, że dwa ostatnie są na swoich miejscach. Powtarzamy więc ten proces tyle razy, ile potrzeba, to znaczy \(n - 1\) razy, jako, że jak ustawimy wszystkie oprócz jednego w odpowiedniej kolejności, to znaczy, że ten pierwszy, też będzie w odpowiedniej kolejności, bo zawsze zaczynamy nasze przejście od pierwszego elementu.
W praktyce, algorytm prezentuje się następująco:
template<typename T>
void bubble_sort(std::vector<T>& vector) {
if (vector.size() <= 1) {
return;
}
for (size_t iteration = 0; iteration < vector.size() - 1; iteration++) {
for (size_t index = 0; index < vector.size() - 1 - iteration; index++) {
if (vector[index] > vector[index + 1]) {
std::swap(vector[index], vector[index + 1]);
}
}
}
}
def bubble_sort(vector: list):
for iteration in range(len(vector) - 1):
for index in range(len(vector) - 1 - iteration):
if vector[index] > vector[index + 1]:
vector[index], vector[index + 1] = vector[index + 1], vector[index]Wizualizacja
By ułatwić zrozumienie tego, jak ten algorytm działa, przygotowałem małą wizualizację. Zachęcam do jej użycia, gdy będziecie analizowali, lub potrzebowali pomocy przy samodzielnej implementacji:
Wpisz elementy do posortowania, np: 1, 2, 3, 4
Złożoność czasowa
Przeliczmy sobie jego złożoność. Robiliśmy to już przy artykule o maszynie ram, ale dla porządku i żeby mieć wszystko w jednym miejscu, zróbmy to jeszcze raz, ale w trochę praktyczniejszy sposób. Skupmy się na najważniejszych aspektach/operacjach, które będziemy wykonywać, a które będą miały dla nas największe znaczenie. A więc:
- Ile razy musimy dostać się do pamięci naszego ciągu,
- Ile razy będziemy porównywać elementy,
- Ile razy trzeba będzie je zamieniać
Te aspekty idealnie wyabstrahują nam nad wszelkie implementacje i języki, to jak dużo operacji będzie wykonywał nasz algorytm. Przejdźmy więc do liczenia.
Porównania.
W tym przypadku nie musimy zakładać żadnego scenariusza, ponieważ ten algorytm jest na tyle prosty, że też nic nie zakłada. Jedzie po kolei bez myślenia, najpierw od \(1\) do \(n - 1\), potem od \(1\) do \(n - 2\), za każdym razem wykonując o jedno mniej porównanie. Za pierwszym przelotem \(n - 1\), za drugim \(n - 2\), by na koniec wykonać jedno porównanie. Sumując więc wszystkie mamy:
\((n - 1) + (n - 2) + (n - 3) + ... + 1 = n(n - 1)\)
Zamiany.
Teraz musimy założyć najgorszy scenariusz, czyli zupełnie odwróconą kolejność ciągu wejściowego. Zakładamy więc, że dla każdego porównania, będzie wykonywana zamiana. Mając więc \(n(n - 1)\) porównań, będziemy mieli też \(n(n - 1)\) zamian.
Dostępy.
Dla każdego porównania potrzebujemy dostępu do \(2\) elementów. Dla każdej zamiany potrzebujemy dostępu do \(2\) elementów, ale łącznie użyjemy \(3\). Raz żeby odczytać pierwszą wartość i ją zachować, dwa, żeby zapisać drugą pod pierwsze miejsce, i trzy, żeby zapisać pierwszą pod drugie miejsce. Mamy więc \(2\) dostępy do \(n(n - 1)\) porównań oraz \(3\) dla \(n(n - 1)\) zamian.
Suma
Zliczając więc wszystko razem. Porównania + Zamiany + Dostępy:
\(n(n - 1) + n(n - 1) + 2\cdot n(n - 1) + 3\cdot n(n - 1)\)
Wymnażając:
\(n^2 - n + n^2 - n + 2n^2 - 2n + 3n^2 - 3n\)
Redukując:
\(7n^2 - 7n\)
A więc funkcja złożoności wynosi:
\(O(7n^2 - 7n) = O(n^2)\)
Złożonośc pamięciowa
Jak widzimy, algorytm ten sortuje w miejscu, więc jego złożoność pamięciowa wynosi \(O(1)\).
Złożoność średnia i najgorszego przypadku
Złożoność średnia będzie taka sama jak najgorszego przypadku. Wynika to z tego, że algorytmu nie interesuje nic poza naginaniem po wszystkich elementach i sprawdzaniem ich wszystkich. W przypadku najlepszego przypadku, zmienia się tylko liczba zamian, więc złożoność nadal pozostaje kwadratowa.
Rekursywność/Rekurencyjność
Algorytm nie jest rekursywny, ponieważ nie używa rekurencji.
Stabilność
Algorytm ten jest stabilny, jako, że nie zamienia elementów, których nie musi, pozostawiając je tam, gdzie je zastał.
Możliwość zrównoleglenia
Nie będzie to możliwe, ze względu na fakt, że podzielenie zestawu danych na mniejsze, sprawi, że posortujemy tylko te zestawy i nadal trzeba będzie posortować całość od nowa.
Adaptacyjność
Również nie będzie adaptacyjny, ponieważ nie zważając na nic, zawsze wykonuje wszystkie przejścia.
Strumieniowość/Ciagłość
Tutaj można to kryterium potwierdzić, jako, że idąc jeden po jednym, zawsze będziemy przechodzić wszystkie elementy, plasując największy na końcu. Trzeba by jednak trochę zmodyfikować jego działanie, więc można by się troszkę kłócić. Załóżmy więc, że nie jest.
Metoda
Tutaj będziemy przestawiać.
Porównanie i brak porównań
Oczywiście, jest to algorytm porównujący.
Inne
Tutaj np. możemy dać trywialność implementacji.
Sortowanie przez wstawianie
Drugim przykładem, bardziej praktycznym, bo rzeczywiście używanym, jest sortowanie przez wstawianie. Jego koncept jest również bardzo prosty. Tym razem jednak, będziemy trochę inaczej podchodzić do zagadnienia. Będziemy iść od początku ciągu, sprawdzając, czy element, który mamy jest większy/mniejszy niż jego poprzednik, i przestawiać go dopóki taki nie będzie. Mamy więc taki zestaw kroków:
- Porównaj \(2\) element z \(1\)
- Jeżeli \(2\) mniejszy niż \(1\), zamień je miejscami
- Jeżeli nie, zakończ przejście
- Porównaj \(3\) element z \(2\)
- Jeżeli \(3\) mniejszy niż \(2\), zamień je miejscami
- Porównaj \(2\) element z \(1\)
- Jeżeli \(2\) mniejszy niż \(1\), zamień je miejscami
- Jeżeli nie, zakończ przejście
- Jeżeli nie, zakończ przejście
- Porównaj \(n\) element z \(n - 1\)
- Jeżeli \(n\) mniejszy niż \(n - 1\), zamień je miejscami
- Porównaj \(n - 1\) element z \(n - 2\)
- Jeżeli \(n - 1\) mniejszy niż \(n - 2\), zamień je miejscami
- Jeżeli nie, zakończ przejście
- ...
- Jeżeli nie, zakończ przejście
Po każdym przejściu mamy pewność, że przynajmniej \(1 + \text{przejście}\) elementów są ustawione w kolejności. Musimy więc wykonać \(n - 1\) przejść, by nasz ciąg posortować. W praktyce, algorytm prezentuje się następująco:
template<typename T>
void insertion_sort(std::vector<T>& vector) {
if (vector.size() <= 1) {
return;
}
for (size_t iteration = 1; iteration < vector.size(); iteration++) {
for (size_t index = iteration; index >= 1; index--) {
if (vector[index - 1] < vector[index]) {
std::swap(vector[index - 1], vector[index]);
} else {
break;
}
}
}
}def insertion_sort(vector: list):
for iteration in range(len(vector)):
for index in range(iteration, 0, -1):
if vector[index - 1] < vector[index]:
vector[index], vector[index - 1] = vector[index - 1], vector[index]
else:
breakDlaczego więc nazywamy go sortowaniem przez wstawianie? Ano dlatego, że koncepcyjnie, algorytm wyciąga aktualnie przetwarzany element z ciągu i "szuka mu miejsca" by go z powrotem wstawić. W praktyce takie coś jest zupełnie bez sensu, bo zmusza nas do kosztownych przekształceń struktur, jak. np realokacja i kopiowanie, więc sobie bez tego niepotrzebnego wysiłku po prostu przestawiamy ten element i tak szukamy mu miejsca.
Wizualizacja
Tak jak poprzednio, by ułatwić zrozumienie tego, jak ten algorytm działa, przygotowałem małą wizualizację. Zachęcam do jej użycia, gdy będziecie analizowali, lub potrzebowali pomocy przy samodzielnej implementacji:
Wpisz elementy do posortowania, np: 1, 2, 3, 4
Złożoność czasowa
Bez większych wstępów, do liczenia.
Porównania.
W tym przypadku nie musimy założyć najgorszy scenariusz, ponieważ w przeciwieństwie do bąbelkowego, ten algorytm ma pomysł jak nie robić czegoś, czego nie musi robić. Będzie od elementu, w lewo, szukał swojego miejsca i wykona tyle porównań ile będzie musiał. Przy najgorszym przypadku (odwrotnie do porządanego posortowany ciąg) wykona wszystkie od aktualnie przetwarzanego elementu, do pierwszego, czyli \(1\) w pierwszym przejściu, \(2\) w drugim, itd. aż do \(n - 1\) w ostatnim. Sumując więc:
\(1 + 2 + 3 + \space ... \space + (n - 1) = n(n - 1)\)
Zamiany.
Znów musimy założyć najgorszy scenariusz. Zakładamy więc, że dla każdego porównania, będzie wykonywana zamiana. Mając więc \(n(n - 1)\) porównań, będziemy mieli też \(n(n - 1)\) zamian.
Dostępy.
Dla każdego porównania potrzebujemy dostępu do \(2\) elementów. Dla każdej zamiany potrzebujemy dostępu do \(2\) elementów, ale łącznie użyjemy \(3\). Raz żeby odczytać pierwszą wartość i ją zachować, dwa, żeby zapisać drugą pod pierwsze miejsce, i trzy, żeby zapisać pierwszą pod drugie miejsce. Mamy więc \(2\) dostępy do \(n(n - 1)\) porównań oraz \(3\) dla \(n(n - 1)\) zamian.
Suma
Zliczając więc wszystko razem. Porównania + Zamiany + Dostępy:
\(n(n - 1) + n(n - 1) + 2\cdot n(n - 1) + 3\cdot n(n - 1)\)
Wymnażając:
\(n^2 - n + n^2 - n + 2n^2 - 2n + 3n^2 - 3n\)
Redukując:
\(7n^2 - 7n\)
A więc funkcja złożoności wynosi:
\(O(7n^2 - 7n) = O(n^2)\)
Złożonośc pamięciowa
Jak widzimy, algorytm ten sortuje w miejscu, więc jego złożoność pamięciowa wynosi \(O(1)\).
Złożoność średnia i najgorszego przypadku
Złożoność średnia będzie taka sama jak najgorszego przypadku. Wynika to z analiz, których nie będę teraz przytaczał.
Rekursywność/Rekurencyjność
Algorytm nie jest rekursywny, ponieważ nie używa rekurencji.
Stabilność
Algorytm ten jest stabilny, jako, że nie zamienia elementów, których nie musi, pozostawiając je tam, gdzie je zastał.
Możliwość zrównoleglenia
Nie będzie to możliwe, ze względu na fakt, że podzielenie zestawu danych na mniejsze, sprawi, że posortujemy tylko te zestawy i nadal trzeba będzie posortować całość od nowa.
Adaptacyjność
Algorytm będzie adaptacyjny, ponieważ im bardziej posortowana będzie struktura, tym mniej będzie musiał robić.
Strumieniowość/Ciagłość
Jak najbardziej to kryterium jest spełnione, ponieważ każdy dołożony na koniec element, będzie po prostu kolejnym przebiegiem algorytmu.
Metoda
Tutaj będziemy przestawiać ale na upartego, można to nazwać wstawianiem.
Porównanie i brak porównań
Oczywiście, jest to algorytm porównujący.
Inne
Tutaj np. możemy dać trywialność implementacji. Wspomniałem wcześniej również, że ten algorytm jest wykorzystywany w normalnych, poważnych implementacjach. I jest to prawda. Sortowanie przez wstawianie jest, ze względu na prostotę, jednym z najlepszych algorytmów do sortowania małych ciągów, dlatego jest używana jako krok w bardziej złożonych algorytmach, takich jak np. sortowanie szybkie. Oprócz tego, skomplikowane algorytmy, takie jak np. sortowanie przez scalanie, są dużo lepsze dla dużych ciągów, tak dla małych złożoność implementacji algorytmu sprawia, że jest on wolniejszy od sortowania przez wstawianie dla małych ciągów.
Podsumowanie
Jak widzimy problem w zasadzie dosyć prosty, wcale taki nie jest. Rozłożywszy go jednak na czynniki pierwsze, widzimy, że jest do ogarnięcia, mało tego, jest niezwykle ciekawy przez to, że rozwiązuje realny problem z jakim borykamy się na co dzień. W dalszych artykułach, gdy będziemy kontynuować rozważania na temat algorytmów, przedstawimy więcej ich wariantów, oraz opiszemy inne podejścia niż opisane w naszych tutaj przykładach. Dziękuję za uwagę i do zobaczenia w następnych artykułach! :)
Komentarze