Sortowanie przez wstawianie

Istnieje wiele sposobów sortowania. Przy sortowaniu poprzez wybór, początek tablicy jest posortowany, a koniec nie. Sortowanie przez wybór skanuje nieposortowaną podtablicę, aby znaleźć następny element, który dołączy do posortowanej części tablicy.

Oto inny sposób myślenia o sortowaniu. Wyobraź sobie, że grasz w karty. Trzymasz karty w ręku i są one posortowane. Rozdający podaje ci dokładnie jedną nową kartę. Musisz ją włożyć we właściwe miejsce, tak aby karty, które trzymasz wciąż były posortowane. W sortowaniu przez wybór, każdy element, który dodawałeś do posortowanej podtablicy był nie mniejszy niż elementy już znajdujące się w niej. Ale w naszym przykładzie z kartami, nowa karta może być mniejsza niż te, które już trzymasz w ręku. W związku z tym, musisz spoglądać na karty od najwyższej do najniższej, porównując nową kartę z każdą trzymaną w ręku, aż znajdziesz odpowiednie dla niej miejsce. Wkładasz nową kartę we właściwe miejsce i wciąż trzymasz w ręku karty ułożone w kolejności. Następnie rozdający, daje ci kolejną kartę, a ty powtarzasz tę samą procedurę. A potem następną kartę i następną, i tak dalej - aż rozdający skończy rozdawanie kart.

Taka jest właśnie idea sortowania przez wstawianie.. Przechodź w pętli przez kolejne pozycje tablicy, rozpoczynając od indeksu 1. Każda nowa pozycja jest jak nowa karta, którą otrzymujesz od rozdającego i musisz ją wstawić we właściwe miejsce w posortowaną podtablicę - po lewej stronie. Oto wizualizacja powyższych kroków:

Przekładając to na język "tablic": wyobraź sobie, że podtablica od indeksu 0 do indeksu $5$5 jest już posortowana i chcemy wstawić element bieżący w indeksie 6 w tej posortowanej podtablicy tak by teraz podtablica od indeksu 0 do indeksu 6 była posortowana. Oto jak zaczniemy:

A oto jak będzie wyglądać podtablica, gdy skończymy:

Aby wstawić element z pozycji 6 do posortowanej podtablicy po jego lewej stronie, porównujemy go z każdym elementem po jego lewej stronie, idąc od prawej do lewej. Element na 6 pozycji nazwijmy kluczem. Za każdym razem, gdy okaże się, że klucz jest mniejszy niż element po jego lewej stronie, przesuwamy ten element o jedną pozycję w prawą stronę, ponieważ wiemy, że klucz będzie musiał przesunąć się na lewą stronę tego elementu. Będziemy potrzebować dwóch rzeczy, aby ten sposób zadziałał: potrzebujemy wykonać operację przesunięcia, która przesuwa element o jedną pozycję w prawo oraz potrzebujemy zapamiętać wartość klucza w osobnym miejscu (tak, aby nie została ona nadpisana przez element przesuwany). W naszym przykładzie, przypiszmy wartość elementu znajdującego się w tablicy pod indeksem 6, zmiennej key (klucz):

Teraz, porównujemy tą zmienną klucz z elementem na pozycji 5. Widzimy, że klucz (5) jest mniejszy niż element na pozycji 5 (13), więc przesuwamy ten element na pozycję 6:

Zauważ, że operacja przesunięcia polega na prostym skopiowaniu elementu o jedną pozycję w prawo. Następnie, porównujemy klucz z elementem na pozycji 4. Widzimy, że klucz(5) jest mniejszy niż element na pozycji 4 (10), więc przesuwamy ten element w prawo:

Następnie, porównujemy klucz z elementem na pozycji 3 i przesuwamy ten element:

To samo dzieje się z elementem na pozycji 2:

Teraz jesteśmy przy elemencie na pozycji 1, który ma wartość 3. Ten element jest mniejszy niż klucz, więc go nie przesuwamy w prawo. Zamiast tego, wstawiamy klucz na pozycję po prawej stronie tego elementu (czyli na pozycję 2), skąd w kroku wcześniejszym przesunęliśmy element na pozycję 3. Wynikiem naszych działań jest posortowana podtablica od indeksu 0 do 6:

Sortowanie przez wstawianie, poprzez powtarzanie czynności, wstawia element do posortowanej podtablicy z lewej strony. Początkowo, możemy powiedzieć, że podtablica posiadająca tylko indeks 0 jest posortowana, gdyż zawiera tylko jeden element. Jak mógłby on być nie posortowany w stosunku do samego siebie? Musi być posortowana. Pokażmy to na przykładzie. Oto nasza początkowa tablica:

Ponieważ podtablica zawierająca jedynie indeks 0 jest naszą początkową uporządkowaną podtablicą, pierwszy klucz znajduje się w indeksie 1. (Posortowana podtablica zaznaczona jest kolorem czerwonym, klucz - kolorem żółtym, a część tablicy, którą musimy wstawić - kolorem niebieskim.) Wstawiamy klucz w posortowaną podtablicę po jego lewej stronie:

Teraz posortowana podtablica obejmuje indeks 0 i 1, a nowy klucz znajduje się w indeksie 2. Wstawiamy go do posortowanej tablicy po jego lewej stronie:

Kontynuujemy nasze postępowanie, kolejno traktując każdy element niebieskiej tablicy jako klucz i wstawiając go do posortowanej podtablicy po jego lewej stronie:

Kiedy już wstawiliśmy ostatni element z prawej strony tablicy, cała tablica okazuje się być posortowana:

Kilka sytuacji, które pojawiły się w naszym przykładzie, potrzebuje dokładniejszej analizy: gdy klucz, który jest wstawiany jest mniejszy niż wszystkie elementy po jego lewej stronie (jak w sytuacji, gdy wstawialiśmy klucze: 2 i 3) oraz kiedy klucz jest większy lub równy wszystkim elementom po jego lewej stronie (jak w sytuacji, gdy wstawialiśmy klucz 13). W pierwszym przypadku, każdy element podtablicy po lewej stronie od klucza, musi być przesunięty w prawo i musimy zatrzymać się, gdy dojdziemy do lewego końca tablicy. W drugim przypadku, gdy pierwszy raz porównujemy klucz z elementem po jego lewej stronie, widzimy, że klucz już znajduje się w odpowiedniej pozycji w stosunku do pozostałych elementów po jego lewej stronie; żaden element nie musi być przesuwany i klucz zostaje w pozycji, w której zaczęliśmy operację porównywania.

Głównym krokiem w sortowaniu przez wstawianie jest zrobienie miejsca w tablicy na wstawienie bieżącej wartości, która jest przechowywana w zmiennej klucz. Jak widzieliśmy wcześniej, idziemy przez podtablicę z lewej strony zmiennej klucz - od prawej do lewej, przesuwając każdy element, który jest większy od zmiennej klucz, o jedną pozycję w prawo. Gdy już znajdziemy element mniejszy od zmiennej klucz lub równy zmiennej klucz, zatrzymujemy przesuwanie elementów i kopiujemy klucz na wolne miejsce - po prawej stronie tego elementu. (Oczywiście, to miejsce nie jest tak naprawdę wolne, ale ten element został już przesunięty w prawo.) Poniższy diagram pokazuje ideę tego wstawiania:

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.