DAA - Ekleme Sıralaması

Ekleme sıralaması, sayıları artan veya azalan düzende sıralamak için çok basit bir yöntemdir. Bu yöntem artımlı yöntemi izler. Oyun oynarken kartların nasıl sıralandığı teknikle karşılaştırılabilir.

Sıralanması gereken sayılar şu şekilde bilinir: keys. Eklemeli sıralama yönteminin algoritması aşağıda verilmiştir.

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

Analiz

Bu algoritmanın çalışma süresi, verilen girişe büyük ölçüde bağlıdır.

Verilen sayılar sıralanırsa, bu algoritma O(n)zaman. Verilen sayılar ters sıradaysa, algoritmaO(n²) zaman.

Misal

Unsorted list:

2 13 5 18 14

1^st iteration:

Anahtar = a [2] = 13

a [1] = 2 <13

Takas, takas yok

2 13 5 18 14

2^nd iteration:

Anahtar = a [3] = 5

a [2] = 13> 5

5 ile 13'ü değiştirin

2 5 13 18 14

Sonra, a [1] = 2 <13

Takas, takas yok

2 5 13 18 14

3^rd iteration:

Anahtar = a [4] = 18

a [3] = 13 <18,

a [2] = 5 <18,

a [1] = 2 <18

Takas, takas yok

2 5 13 18 14

4^th iteration:

Anahtar = a [5] = 14

a [4] = 18> 14

18 ve 14'ü değiştirin

2 5 13 14 18

Sonra, a [3] = 13 <14,

a [2] = 5 <14,

a [1] = 2 <14

Yani takas yok

2 5 13 14 18

En sonunda,

the sorted list is

2 5 13 14 18