Lekcja: "Algorytmy sortujące - sortowanie przez wstawianie, sortowanie przez wybór"
Sortowanie przez wstawianie - Insertion Sort
Jest to prosty algorytm sortowania, o złożoności O(n2), sortowanie odbywa się w miejscu. Mimo że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy heapsort posiada pewne zalety:
wydajny dla danych wstępnie posortowanych
wydajny dla zbiorów o niewielkiej liczebności
stabilny
Algorytm polega na usuwaniu pewnego elementu z danych wejściowych i wstawianiu go na odpowiednie miejsce w wynikach. Wybór następnego elementu z danych jest dowolny.