Sortowanie przez wstawianie

Na czym polega sortowanie przez wstawianie?

Na podstawie książki T. H. Cormen i in. ,,Wprowadzenie do algorytmów’': Sortowanie przez wstawianie jest efektywnym algorytmem sortowania dla niewielkiej liczby elementów. Algorytm ten działa w taki sposób, jaki ludzie często porządkują rozdane karty. Zaczynamy od ,,pustej’’ lewej ręki i kupki kart zakrytych na stole. Następnie bierzemy ze stołu kolejno po jednej karcie i wstawiamy ją we właściwe miejsce wśród kart trzymanych w lewej ręce. Aby znaleźć włąściwe miejsce dla danej karty, porównujemy ją z kartami, które już mamy w ręce, przeglądając je od strony prawej do lewej. Przez cały czas karty trzymane w lewej ręce są posortowane, a kart na stole znajdują się w losowej kolejności.

Wizualizacja

Pseudokod

procedure insertionSort( A : lista elementów do posortowania )
  n = liczba_elementów(A)
  for (i = 1; i < n; i++) do
    key = A[i]
    //Wstaw A[j] w posortowany ciąg A[0:i]
    j = i - 1
    while (j >= 0) and (A[j] > key)
      A[j+1] = A[j]
      j -= 1
    A[i+1] = key

Co należy zaimplementować?

1. Zaimplementuj funkcję insert_sort(), która jako argument przyjmuje listę a zwraca listę posortowaną.
2. W funkcji main() wygeneruj losową listę liczb o długości N=1000.
3. Posortuj tę listę wykorzystując insert_sort().
4. Sprawdź czy lista zwrócona przez funkcję jest posortowana.
5. Zmierz czas potrzebny na wykonanie sortowania N = {10, 100, 1000, 10000} liczb.

Pytania

1. Jak rośnie czas wykonania algorymtu wraz ze wzrostem długości danych N (liniowo, kwadratowo, logarytmicznie, …)?
2. Czy masz jakieś pomysły na usprawnienie sortowania przez wstawianie (zmniejszenie liczby porównań, zmiejszenie liczy przestawień)?