DAA - Sortowanie przez wstawianie

Sortowanie przez wstawianie to bardzo prosta metoda sortowania liczb w kolejności rosnącej lub malejącej. Ta metoda jest zgodna z metodą przyrostową. Można to porównać z techniką sortowania kart podczas gry.

Liczby, które należy posortować, nazywane są keys. Oto algorytm metody sortowania przez wstawianie.

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

Analiza

Czas działania tego algorytmu jest bardzo zależny od danych wejściowych.

Jeśli podane liczby są posortowane, działa ten algorytm O(n)czas. Jeśli podane liczby są w odwrotnej kolejności, algorytm działaO(n²) czas.

Przykład

Unsorted list:

2 13 5 18 14

1^st iteration:

Klucz = a [2] = 13

a [1] = 2 <13

Swap, no swap

2 13 5 18 14

2^nd iteration:

Klucz = a [3] = 5

a [2] = 13> 5

Zamień 5 i 13

2 5 13 18 14

Następnie a [1] = 2 <13

Swap, no swap

2 5 13 18 14

3^rd iteration:

Klucz = a [4] = 18

a [3] = 13 <18,

a [2] = 5 <18,

a [1] = 2 <18

Swap, no swap

2 5 13 18 14

4^th iteration:

Klucz = a [5] = 14

a [4] = 18> 14

Zamień 18 i 14

2 5 13 14 18

Następnie a [3] = 13 <14,

a [2] = 5 <14,

a [1] = 2 <14

Więc nie ma zamiany

2 5 13 14 18

Wreszcie,

the sorted list is

2 5 13 14 18