Istnieje kilka podstawowych algorytmów rozwiązywania problemu sortowania tablicy. Jednym z najbardziej znanych jest sortowanie przez wstawianie. Ze względu na swoją klarowność i prostotę, ale małą wydajność, metoda ta jest wykorzystywana głównie w nauczaniu programowania. Pozwala zrozumieć podstawowe mechanizmy sortowania.
Opis algorytmu
Istota algorytmu sortowania przez wstawianie polega na tym, że wewnątrz tablicy początkowej tworzony jest odpowiednio uporządkowany segment. Każdy element jest porównywany jeden po drugim ze sprawdzaną częścią i wstawiany we właściwe miejsce. W ten sposób po przejściu przez wszystkie elementy układają się one we właściwej kolejności.
Kolejność wybierania elementów może być dowolna, mogą być wybierane dowolnie lub według jakiegoś algorytmu. Najczęściej stosuje się wyliczanie sekwencyjne od początku tablicy, w której tworzony jest uporządkowany segment.
Początek sortowania może wyglądać tak:
- Pobierz pierwszy element tablicy.
- Ponieważ nie ma z czym porównywać, weź sam element w kolejnościsekwencja.
- Przejdź do drugiej pozycji.
- Porównaj to z pierwszym w oparciu o regułę sortowania.
- W razie potrzeby zamień elementy w miejscach.
- Weź pierwsze dwa elementy jako uporządkowaną sekwencję.
- Przejdź do trzeciej pozycji.
- Porównaj to z drugim, w razie potrzeby zamień.
- Jeśli dokonano wymiany, porównaj ją z pierwszą.
- Weź trzy elementy jako uporządkowaną sekwencję.
I tak dalej aż do końca oryginalnej tablicy.
Sortowanie wstawiania z prawdziwego życia
Dla jasności warto podać przykład wykorzystania tego mechanizmu sortowania w życiu codziennym.
Weź na przykład portfel. Setki, pięćset i tysiącdolarowe banknoty leżą w nieładzie w przegródce na banknoty. To bałagan, w takiej mieszaninie trudno od razu znaleźć odpowiednią kartkę papieru. Tablica banknotów musi być posortowana.
Pierwszy banknot o wartości 1000 rubli, a zaraz po nim - 100. Bierzemy sto i kładziemy z przodu. Trzeci z rzędu to 500 rubli, należne mu miejsce to od stu do tysiąca.
W ten sam sposób sortujemy otrzymane karty podczas gry w "Głupca", aby ułatwić nawigację po nich.
Operatory i funkcje pomocnicze
Metoda sortowania przez wstawianie przyjmuje jako dane wejściowe tablicę początkową do posortowania, funkcję porównania i, jeśli to konieczne, funkcję określającą regułę wyliczania elementów. Najczęściej używane zamiastinstrukcja pętli regularnej.
Pierwszy element sam w sobie jest uporządkowanym zestawem, więc porównanie zaczyna się od drugiego.
Algorytm często używa funkcji pomocniczej do wymiany dwóch wartości (swap). Używa dodatkowej zmiennej tymczasowej, która zużywa pamięć i nieco spowalnia kod.
Alternatywą jest masowe przesunięcie grupy elementów, a następnie wstawienie bieżącego w wolne miejsce. W takim przypadku przejście do kolejnego elementu następuje, gdy porównanie dało wynik dodatni, co wskazuje na prawidłową kolejność.
Przykłady realizacji
Konkretna implementacja w dużej mierze zależy od używanego języka programowania, jego składni i struktur.
Implementacja w klasycznym C używająca tymczasowej zmiennej do wymiany wartości:
int i, j, temp; for (i=1; i =0; j--) { if (tablica[j] < temp) przerwa; tablica[j + 1]=tablica[j]; tablica[j]=temp; } }
Wdrożenie PHP:
function insert_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Tutaj najpierw wszystkie elementy, które nie spełniają warunku sortowania, są przesuwane w prawo, a następnie bieżący element jest wstawiany w wolne miejsce.
Kod Java przy użyciu pętli while:
public static void insertSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=curElem; prevKey--; } } }
Ogólne znaczenie kodu pozostaje niezmienione: każdy element tablicy jest sekwencyjnie porównywany z poprzednimi i w razie potrzeby zamieniany z nimi.
Szacowany czas pracy
Oczywiście, w najlepszym przypadku, wejście algorytmu będzie tablicą już uporządkowaną we właściwy sposób. W takiej sytuacji algorytm będzie musiał po prostu sprawdzić każdy element, aby upewnić się, że znajduje się we właściwym miejscu bez dokonywania wymian. Zatem czas działania będzie bezpośrednio zależał od długości oryginalnej tablicy O(n).
Najgorszy przypadek to tablica posortowana w odwrotnej kolejności. Będzie to wymagało dużej liczby permutacji, funkcja uruchomieniowa będzie zależeć od liczby elementów do kwadratu.
Dokładną liczbę permutacji dla całkowicie nieuporządkowanej tablicy można obliczyć za pomocą wzoru:
n(n-1)/2
gdzie n jest długością oryginalnej tablicy. Ułożenie 100 elementów we właściwej kolejności wymagałoby zatem 4950 permutacji.
Metoda wstawiania jest bardzo wydajna przy sortowaniu małych lub częściowo posortowanych tablic. Nie zaleca się jednak stosowania go wszędzie ze względu na dużą złożoność obliczeń.
Algorytm jest używany jako pomoc w wielu innych, bardziej złożonych metodach sortowania.
Sortuj równe wartości
Algorytm wstawiania należy do tak zwanych sortowań stabilnych. To znaczy,że nie zamienia identycznych elementów, ale zachowuje ich pierwotną kolejność. Wskaźnik stabilności jest w wielu przypadkach ważny dla prawidłowego zamówienia.
Powyższe jest świetnym wizualnym przykładem sortowania wstawiania w tańcu.
