Veri Yapısı ve Algoritmalar Ekleme Sıralaması

Bu, yerinde karşılaştırma tabanlı bir sıralama algoritmasıdır. Burada, her zaman sıralanan bir alt liste tutulur. Örneğin, bir dizinin alt kısmı sıralanacak şekilde tutulur. Bu sıralı alt listeye 'eklenecek' bir eleman uygun yerini bulmalı ve sonra oraya eklenmelidir. Dolayısıyla adıinsertion sort.

Dizi sıralı olarak aranır ve sıralanmamış öğeler taşınır ve sıralı alt listeye (aynı dizide) eklenir. Ortalama ve en kötü durum karmaşıklığı Ο (n ² ) olduğundan, bu algoritma büyük veri kümeleri için uygun değildir.n öğe sayısıdır.

Ekleme Sıralaması Nasıl Çalışır?

Örneğimiz için sıralanmamış bir dizi alıyoruz.

Ekleme sıralaması, ilk iki öğeyi karşılaştırır.

Hem 14 hem de 33'ün zaten artan sırada olduğunu bulur. Şimdilik, 14 alt listede sıralanmıştır.

Ekleme sıralaması ilerler ve 33 ile 27'yi karşılaştırır.

Ve 33'ün doğru konumda olmadığını bulur.

33 ile 27'yi değiştirir. Ayrıca sıralanmış alt listenin tüm elemanlarını kontrol eder. Burada, sıralanan alt listenin yalnızca bir öğeye 14 sahip olduğunu ve 27'nin 14'ten büyük olduğunu görüyoruz. Dolayısıyla, sıralanan alt liste, değiştirildikten sonra sıralı olarak kalır.

Şimdiye kadar sıralanmış alt listede 14 ve 27 var. Sonra 33'ü 10 ile karşılaştırır.

Bu değerler sıralı bir düzende değildir.

Bu yüzden onları değiştiriyoruz.

Ancak, takas, 27 ve 10'u sıralanmamış yapar.

Bu nedenle, onları da değiştiriyoruz.

Yine sıralanmamış bir sırada 14 ve 10'u buluyoruz.

Onları tekrar değiştiriyoruz. Üçüncü yinelemenin sonunda, 4 öğeden oluşan bir alt listeye sahibiz.

Bu işlem, tüm sıralanmamış değerler sıralı bir alt listede kapsanana kadar devam eder. Şimdi, ekleme sıralamanın bazı programlama yönlerini göreceğiz.

Algoritma

Şimdi, bu ayırma tekniğinin nasıl çalıştığına dair daha büyük bir resme sahibiz, böylece araya yerleştirme sıralaması elde edebileceğimiz basit adımlar türetebiliriz.

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Sözde kod

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
	
   for i = 1 to length(A) inclusive do:
	
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
		
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
		
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
	
end procedure

C programlama dilinde araya ekleme sıralaması uygulaması hakkında bilgi edinmek için lütfen buraya tıklayın .