Algorytmy sortujące

Sortowanie przez wstawianie

Algorytm sortowania przez wstawianie można porównać do sposobu układania kart pobieranych z talii. Najpierw bierzemy pierwszą kartę. Następnie pobieramy kolejne, aż do wyczerpania talii. Każdą pobraną kartę porównujemy z kartami, które już trzymamy w ręce i szukamy dla niej miejsca przed pierwszą kartą starszą (młodszą w przypadku porządku malejącego). Gdy znajdziemy takie miejsce, rozsuwamy karty i nową wstawiamy na przygotowane w ten sposób miejsce (stąd pochodzi nazwa algorytmu – sortowanie przez wstawianie, ang. Insertion Sort). Jeśli nasza karta jest najstarsza (najmłodsza), to umieszczamy ją na samym końcu. Tak porządkujemy karty.

Binarne sortowanie przez wstawianie

Algorytm sortowania przez wstawianie wykorzystuje poszukiwanie liniowe w celu znalezienia miejsca wstawiania wybranego elementu na liście uporządkowanej. Są trzy możliwości:

1. Element wybrany jest mniejszy lub równy pierwszemu elementowi listy uporządkowanej (w porządku malejącym element ten jest większy lub równy). W takim przypadku wykonane zostanie tylko jedno porównanie i element wybrany wróci z powrotem na swoje poprzednie miejsce.

2. Element wybrany jest większy od ostatniego elementu listy uporządkowanej (w porządku malejącym element wybrany jest mniejszy od ostatniego elementu listy uporządkowanej). Jeśli element wybrany znajduje się na j-tej pozycji, to algorytm musi wykonać (n – j) porównań elementy wybranego z kolejnymi elementami listy oraz tyle samo przesunięć elementów listy na puste miejsce.

3. W pozostałych przypadkach element wybrany trafia do wnętrza listy uporządkowanej. Statystycznie będzie to jej środek, zatem średnio algorytm wykona 0,5 • (n – j) porównań i przesunięć elementów.