Sortowanie przez wstawianie / umieszczanie (insertion sort)
Wprowadzenie
Sortowanie przez wstawianie, zwane inaczej sortowaniem przez umieszczanie, podobnie jak sortowanie przez wybór jest jednym z najprostszych do zrozumienia i zaimplementowania w danym języku programowania algorytmem sortowania.
Sprecyzujmy warunki sortowania:
Dane: n elementów oznaczonych x[1], x[2], x[3], ..., x[n] oraz operator porównania
tych elementów, za pomocą którego możemy stwierdzić który z dwóch porównywanych elementów jest mniejszy, a który większy
oraz operator równości, za pomocą którego możemy stwierdzić, kiedy dwa elementy są sobie równe.
Wynik: n elementów uporządkowanych w taki sposób, że pierwszy element jest najmniejszy w sensie
operatora porównania elementów, a ostatni jest elementem największym w sensie tego samego operatora.
Algorytm w postaci listy kroków
-
Dla i od 2 do n wykonaj:
- Jeśli x[i] jest mniejsze od x[1], to liczbie k przypisz 0, w przeciwnym razie znajdź największe k pośród 1, 2, ..., i, takie że x[k] jest mniejsze lub równe x[i]
- Elementy x[k+1],...,x[i-1] przesuń w prawo o jedno miejsce, tak że element x[k+1] znajdzie się na pozycji x[k+2] a element x[i-1] na pozycji x[i]. Element x[i] umieść na pozycji x[k+1]
- Elementy są już posortowane - zakończ algorytm
Analiza algorytmu - dwie tablice
Oto wyjaśnienie algorytmu. Dla ułatwienia zrozumienia, załóżmy, że mamy dwie tablice: tablicę danych x i tablicę wynikową y. Pierwszy element kopiujemy z tablicy x do tablicy y.
Teraz bierzemy element drugi. Musimy stwierdzić gdzie mamy go wstawić, przed czy za pierwszym elementem. Jeśli element ten jest mniejszy od pierwszego elementu tablicy y, to przed wstawieniem, musimy element w tablicy y, przenieść o jedno miejsce w prawo, aby zrobić miejsce dla wstawianego elementu. Jeśli natomiast element jest większy od elementu w tablicy y, to nie musimy nic przenosić. W obu przypadkach wstawiamy element do tablicy y w odpowiednie miejsce.
Teraz bierzemy element trzeci z tablicy x. Jeśli element jest mniejszy od pierwszego elementu w tablicy y, oba elementy w tablicy y, musimy przesunąć o jedno miejsce w prawo, aby wstawić element w pierwsze miejsce. Jeśli natomiast element nie był mniejszy od pierwszego elementu w tablicy y, musimy go porównać z drugim elementem - i jak się zapewne domyślasz, gdyby w tablicy y było więcej elementów, musielibyśmy porównywać do skutku, aby znaleźć odpowiednie miejsce.
Mam nadzieję, że już rozumiesz ideę algorytmu. Główną ideą algorytmu jest wstawianie elementu do już posortowanego ciągu elementów. Za pierwszym razem, tym posortowanym ciągiem elementów jest tylko jeden element, za następnym razem już dwa elementy, a za ostatnim n-1 elementów.
Dzięki temu, że element wstawiamy do posortowanego już ciągu elementów, nie musimy porównywać go z każdym elementem, choć może się zdarzyć (jeśli element będzie większy od wszystkich pozostałych posortowanych elementów), że będziemy musieli porównać bieżący element ze wszystkimi elementami posortowanymi.
