Lekcja: "Algorytmy sortujące - sortowanie przez wstawianie, sortowanie przez wybór"
Schemat działania algorytmu:
Najważniejszą operacją w opisywanym algorytmie sortowania jest wstawianie wybranego elementu na listę uporządkowaną. Zasady są następujące:
Na początku sortowania lista uporządkowana zawiera tylko jeden, ostatni element zbioru.
Jednoelementowa lista jest zawsze uporządkowana.
Ze zbioru zawsze wybieramy element leżący tuż przed listą uporządkowaną. Element ten zapamiętujemy w zewnętrznej zmiennej. Miejsce, które zajmował, możemy potraktować jak puste.
Wybrany element porównujemy z kolejnymi elementami listy uporządkowanej.
Jeśli natrafimy na koniec listy, element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.
Jeśli element listy jest większy od wybranego, to element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.
Jeśli element listy nie jest większy od wybranego, to element listy przesuwamy na puste miejsce. Dzięki tej operacji puste miejsce wędruje na liście przed kolejny element. Kontynuujemy porównywanie, aż wystąpi sytuacja z punktu 4 lub 5.