Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 1
Lekcja 5: Sortowanie przez wstawianieSortowanie 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 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.
Wstawianie elementu do posortowanej tablicy
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.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji