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?
- Diyelim ki, aşağıdaki diziyi sıralamamız gerekiyor.
İlk dizi
(N/2, N/4,… 1
Algoritmamızda aralıklar olarak kabuğun orijinal dizisini kullanıyoruz .
İlk döngüde, dizi boyutu iseN = 8
, aralığındaki öğelerN/2 = 4
karşılaştırılır ve sıralı değilse değiştirilir.- 0. eleman, 4. eleman ile karşılaştırılır.
- 0. elemanı daha sonra 4 olandan daha büyük ise, 4. eleman ilk depolanan
temp
değişken ve0th
elemanın (yani. Daha elemanı) depolanan4th
konum ve eleman depolanantemp
depolanır0th
pozisyonda.Öğ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
- İkinci döngüde, bir aralık
N/4 = 8/4 = 2
alı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. ve2nd
pozisyondaki elemanlar karşılaştırılır. 2. ve0th
konumdaki elemanlar da karşılaştırılır. Dizideki mevcut aralıktaki tüm öğeler karşılaştırılır. - Kalan elemanlar için de aynı süreç devam ediyor.
Tüm öğeleri n / 4 aralığında yeniden düzenleyin
- Son olarak, aralık olduğunda, 1 aralığında yer
N/8 = 8/8 =1
alan 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.