DAA - Sortir Penyisipan

Sortir penyisipan adalah metode yang sangat sederhana untuk mengurutkan angka dalam urutan naik atau turun. Metode ini mengikuti metode inkremental. Ini dapat dibandingkan dengan teknik bagaimana kartu diurutkan pada saat bermain permainan.

Angka-angka, yang perlu diurutkan, dikenal sebagai keys. Berikut adalah algoritma dari metode sortir penyisipan.

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

Analisis

Run time algoritma ini sangat bergantung pada input yang diberikan.

Jika nomor yang diberikan diurutkan, algoritma ini berjalan O(n)waktu. Jika angka yang diberikan dalam urutan terbalik, algoritme berjalanO(n²) waktu.

Contoh

Unsorted list:

2 13 5 18 14

1^st iteration:

Kunci = a [2] = 13

a [1] = 2 <13

Swap, tanpa swap

2 13 5 18 14

2^nd iteration:

Kunci = a [3] = 5

a [2] = 13> 5

Tukar 5 dan 13

2 5 13 18 14

Berikutnya, a [1] = 2 <13

Swap, tanpa swap

2 5 13 18 14

3^rd iteration:

Kunci = a [4] = 18

a [3] = 13 <18,

a [2] = 5 <18,

a [1] = 2 <18

Swap, tanpa swap

2 5 13 18 14

4^th iteration:

Kunci = a [5] = 14

a [4] = 18> 14

Tukar 18 dan 14

2 5 13 14 18

Berikutnya, a [3] = 13 <14,

a [2] = 5 <14,

a [1] = 2 <14

Jadi, tidak ada swap

2 5 13 14 18

Akhirnya,

the sorted list is

2 5 13 14 18