Veri Yapısı ve Algoritmalar - Kabuk Sıralaması

Kabuk sıralama, oldukça verimli bir sıralama algoritmasıdır ve eklemeli sıralama algoritmasına dayanır. Bu algoritma, küçük değer en sağdaysa ve en sola taşınması gerekiyorsa, eklemeli sıralama durumunda olduğu gibi büyük kaydırmaları önler.

Bu algoritma, önce onları sıralamak ve daha sonra daha az aralıklı öğeleri sıralamak için geniş yayılmış öğeler üzerinde ekleme sıralaması kullanır. Bu boşluk olarak adlandırılırinterval. Bu aralık, Knuth formülüne göre hesaplanır:

Knuth Formülü

h = h * 3 + 1
where −
   h is interval with initial value 1

Bu algoritmanın ortalama ve en kötü durum karmaşıklığı boşluk sırasına bağlı olduğundan, bu algoritma orta büyüklükteki veri kümeleri için oldukça etkilidir, en iyi bilineni Ο (n) olup, burada n öğelerin sayısıdır. Ve en kötü durum uzay karmaşıklığı O (n) 'dir.

Shell Sort Nasıl Çalışır?

Kabuk sıralamanın nasıl çalıştığına dair bir fikir sahibi olmak için aşağıdaki örneği ele alalım. Önceki örneklerimizde kullandığımız dizinin aynısını alıyoruz. Örneğimiz ve anlaşılma kolaylığı için 4'lük aralığı alıyoruz. 4 konum aralığında bulunan tüm değerlerin sanal bir alt listesini yapın. İşte bu değerler {35, 14}, {33, 19}, {42, 27} ve {10, 44}

Her alt listedeki değerleri karşılaştırırız ve orijinal dizide (gerekirse) değiştiririz. Bu adımdan sonra, yeni dizi şöyle görünmelidir -

Ardından, 1 aralığını alırız ve bu boşluk iki alt liste oluşturur - {14, 27, 35, 42}, {19, 10, 33, 44}

Gerekirse orijinal dizideki değerleri karşılaştırır ve değiştiririz. Bu adımdan sonra dizi şöyle görünmelidir -

Son olarak, değer 1 aralığını kullanarak dizinin geri kalanını sıralarız. Kabuk sıralaması, diziyi sıralamak için ekleme sıralaması kullanır.

Aşağıda adım adım tasvir verilmiştir -

Dizinin geri kalanını sıralamak için sadece dört takas gerektiğini görüyoruz.

Algoritma

Kabuk sıralama algoritması aşağıdadır.

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

Sözde kod

Aşağıda, kabuk sıralaması için sözde kod verilmiştir.

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

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