Kabuk Sıralaması

Bu eğitimde, kabuk sıralamanın nasıl çalıştığını öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da kabuk sıralamanın çalışma örneklerini bulacaksınız.

Kabuk sıralama, önce öğeleri birbirinden uzakta sıralayan ve sıralanacak öğeler arasındaki aralığı art arda azaltan bir algoritmadır. Ekleme sıralamanın genelleştirilmiş bir versiyonudur.

Kabuk sıralamasında, belirli bir aralıktaki öğeler sıralanır. Öğeler arasındaki aralık, kullanılan sıraya göre kademeli olarak azaltılır. Kabuk sıralamasının performansı, belirli bir girdi dizisi için kullanılan dizi türüne bağlıdır.

Kullanılan optimal dizilerden bazıları şunlardır:

  • Kabuğun orijinal dizisi: N/2 , N/4 ,… , 1
  • Knuth artışları: 1, 4, 13,… , (3k - 1) / 2
  • Sedgewick'in artışları: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Hibbard'ın artışları: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Papernov & Stasevich artışı: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

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

  1. Diyelim ki, aşağıdaki diziyi sıralamamız gerekiyor. İlk dizi
  2. (N/2, N/4,… 1Algoritmamızda aralıklar olarak kabuğun orijinal dizisini kullanıyoruz .
    İlk döngüde, dizi boyutu ise N = 8, aralığındaki öğeler N/2 = 4karşılaştırılır ve sıralı değilse değiştirilir.
    1. 0. eleman, 4. eleman ile karşılaştırılır.
    2. 0. elemanı daha sonra 4 olandan daha büyük ise, 4. eleman ilk depolanan tempdeğişken ve 0thelemanın (yani. Daha elemanı) depolanan 4thkonum ve eleman depolanan tempdepolanır 0thpozisyonda. Öğeleri n / 2 aralığında yeniden düzenleyin
      Bu işlem kalan tüm öğeler için devam eder. Tüm öğeleri n / 2 aralığında yeniden düzenleyin
  3. İkinci döngüde, bir aralık N/4 = 8/4 = 2alınır ve yine bu aralıklarda yer alan elemanlar sıralanır. Öğeleri n / 4 aralığında yeniden düzenleyin
    Bu noktada kafanız karışabilir. Dizideki mevcut aralıktaki tüm öğeler karşılaştırılır.
    4. ve 2ndpozisyondaki elemanlar karşılaştırılır. 2. ve 0thkonumdaki elemanlar da karşılaştırılır. Dizideki mevcut aralıktaki tüm öğeler karşılaştırılır.
  4. Kalan elemanlar için de aynı süreç devam ediyor. Tüm öğeleri n / 4 aralığında yeniden düzenleyin
  5. Son olarak, aralık olduğunda, 1 aralığında yer N/8 = 8/8 =1alan dizi öğeleri sıralanır. Dizi artık tamamen sıralanmıştır. Öğeleri n / 8 aralığında yeniden düzenleyin

Kabuk Sıralama Algoritması

 i <- size / 2n aralığı için shellSort (dizi, boyut) dizideki her "i" aralığı için 1'e kadar "i" aralığındaki tüm öğeleri sıralar shellSort

Python, Java ve C / C ++ Örnekleri

Python Java C C ++ 
# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) ) 
// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); ) 
// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); )

Karmaşıklık

Kabuk sıralama, kararsız bir sıralama algoritmasıdır, çünkü bu algoritma aralıklar arasında bulunan öğeleri incelememektedir.

Zaman Karmaşıklığı

  • En Kötü Durum Karmaşıklığı : Kabuk sıralama için en kötü durum karmaşıklığı her zaman daha küçük veya eşittir . Poonen Teoremine göre, kabuk sıralama için en kötü durum karmaşıklığı, ya da ya da ikisi arasında bir şeydir.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • En İyi Durum Karmaşıklığı : O(n*log n)
    Dizi zaten sıralandığında, her aralık (veya artış) için toplam karşılaştırma sayısı dizinin boyutuna eşittir.
  • Ortalama Durum Karmaşıklığı : O(n*log n)
    Etrafındadır .O(n1.25)

Karmaşıklık, seçilen aralığa bağlıdır. Yukarıdaki karmaşıklıklar, seçilen farklı artış dizileri için farklılık gösterir. En iyi artış sırası bilinmiyor.

Uzay Karmaşıklığı:

Kabuk sıralama için uzay karmaşıklığı O(1).

Kabuk Sıralama Uygulamaları

Kabuk sıralaması şu durumlarda kullanılır:

  • yığın çağırmak ek yüktür. uClibc kütüphanesi bu sıralamayı kullanır.
  • özyineleme bir sınırı aşıyor. bzip2 sıkıştırıcısı bunu kullanır.
  • Ekleme sıralaması, yakın öğeler birbirinden uzak olduğunda iyi performans göstermez. Kabuk sıralama, yakın öğeler arasındaki mesafeyi azaltmaya yardımcı olur. Böylelikle, daha az sayıda takas yapılacaktır.

Ilginç makaleler...