Her iki sıralama tekniği, hızlı sıralama ve birleştirme sıralama, elemanların kümesinin ayrıldığı ve yeniden düzenlendikten sonra birleştirildiği bölme ve fethetme yöntemine dayanır. Hızlı sıralama genellikle büyük bir öğe kümesini sıralamak için birleştirme sıralamasından daha fazla karşılaştırma gerektirir.
Karşılaştırma Tablosu
| Karşılaştırma için temel | Hızlı sıralama | Birleştirme sıralaması |
|---|---|---|
| Dizideki öğelerin bölümlenmesi | Bir eleman listesinin bölünmesi mutlaka ikiye ayrılmaz. | Dizi her zaman ikiye ayrılır (n / 2). |
| En kötü durum karmaşıklığı | O (n2) | O (n log n) |
| İyi çalışıyor | Küçük dizi | Her tür dizide iyi çalışır. |
| hız | Küçük veri kümesi için diğer sıralama algoritmalarından daha hızlı. | Her tür veri setinde tutarlı hız. |
| Ek depolama alanı gereksinimi | Az | Daha |
| verim | Daha büyük diziler için verimsiz. | Daha verimli. |
| Sıralama yöntemi | İç | dış |
Quick Sort'un tanımı
Hızlı sıralama, kısa diziler için hızlı olduğu için yaygın olarak kullanılan sıralama algoritmasıdır. Elementlerin seti, daha fazla bölünmesi mümkün olmayana kadar tekrar tekrar parçalara bölünür. Hızlı sıralama ayrıca bölüm değişimi sıralaması olarak da bilinir. Elemanları bölümlemek için bir anahtar elemanı (pivot olarak bilinir) kullanır. Bir bölüm, anahtar öğeden daha küçük olan öğeleri içerir. Başka bir bölüm, anahtar öğeden daha büyük olan öğeleri içerir. Elemanlar özyinelemeli olarak sıralanır.
A'nın, sıralanması gereken n sayısının A [1], A [2], A [3], …… .., A [n] dizileri olduğunu varsayalım. Hızlı sıralama algoritması, aşağıdaki adımlardan oluşur.
- İlk eleman veya anahtar olarak seçilen herhangi bir rastgele eleman, = A (1) anahtarını varsayar.
- “Low” işaretçisi ikinciye yerleştirilir ve “yukarı” işaretçisi dizinin son elemanına yerleştirilir, yani low = 2 ve yukarı = n;
- Tutarlı bir şekilde, “low” işaretçisini (A [low]> tuşu) olana kadar bir konum kadar artırın.
- Sürekli olarak, "yukarı" işaretçisini (A [yukarı] <= tuşu) olana kadar bir konum kadar azaltın.
- Yukarı yukarı düşükten büyükse A [yukarı] ile A [düşük] değişimi yapın.
- 5. adımdaki koşul başarısız olana kadar (örn. Yukarı <= düşük) 3., ve 5. adımları tekrarlayın, ardından A ile [yukarı] tuşuyla değiştirin.
- Tuşun solundaki elemanlar tuştan daha küçükse ve tuşun sağındaki elemanlar tuştan büyükse, dizi iki alt diziye bölünür.
- Yukarıdaki prosedür, dizinin tamamı sıralanana kadar alt dizilere tekrar tekrar uygulanır.
Avantajlar ve dezavantajlar
İyi bir ortalama durum davranışına sahiptir. Hızlı sıralamadaki çalışma süresi karmaşıklığı, kabarcık sıralama, ekleme sıralama ve seçim sıralama gibi algoritmalardan daha hızlı olması iyidir. Bununla birlikte, karmaşık ve çok özyinelemelidir, bu nedenle büyük diziler için uygun olmamıştır.
Merge Sort'un tanımı
Birleştirme sıralama ayrıca bölme ve fethetme stratejisine dayanan bir dış algoritmadır. Elemanlar, sadece bir element kalana kadar tekrar tekrar alt dizilere (n / 2) ayrılır ve bu da sıralama zamanını önemli ölçüde azaltır. Yardımcı diziyi depolamak için ek depolama kullanır. Birleştirme sıralaması, her iki yarının depolanması için ikisinin kullanıldığı üçüncü diziyi kullanır ve üçüncüsü, son sıralanan listeyi depolamak için kullanılır. Her bir dizi daha sonra tekrarlı olarak sıralanır. Sonunda, alt diziler onu dizinin eleman boyutunda yapmak için birleştirilir. Liste her zaman hızlı sıralamaya benzemeyen sadece yarısına (n / 2) ayrılmıştır.
A, A [1], A [2], ………, A [n] 'ye göre sıralanacak öğelerin n dizisi olsun. Birleştirme sıralama verilen adımları izler.
- A dizisini yaklaşık n / 2 olarak sıralanmış alt diziye 2'ye bölün, bu, (A [1], A [2]), (A [3], A [4]), (A ['daki elemanların ifade ettiği anlamına gelir. k], A [k + 1]), (A [n-1], A [n]) alt dizileri sıralama düzeninde olmalıdır.
- 4 boyutunda sıralanmış alt dizilerin listesini elde etmek için her çift çifti birleştirin; alt dizilerdeki elemanlar da sıralı sıradadır (A [1], A [2], A [3], A [4]), ……, (A [k-1], A [k], A [k + 1], A [k + 2]), ……., (A [n-3], A [n-2], A [n-1], A [n]).
- Adım 2, sadece bir tane n dizilim dizisi olana kadar art arda gerçekleştirilir.
Avantajlar ve dezavantajlar
Birleştirme sıralama algoritması, sıralamada yer alan öğelerin sayısına bakılmaksızın tam olarak aynı ve kesin şekilde çalışır. Büyük veri setiyle bile iyi çalışır. Ancak, belleğin daha büyük bir bölümünü tüketir.
Hızlı Sıralama ve Birleştirme Sıralama Arasındaki Temel Farklar
- Birleştirme sıralamasında, dizinin yalnızca iki yarıya bölünmesi gerekir (yani n / 2). Buna karşılık olarak, hızlı sıralamada listeyi eşit elemanlara bölme zorunluluğu yoktur.
- Çabuk sıralamada en kötü durum karmaşıklığı, en kötü durumda çok daha fazla karşılaştırma yapıldığından O (n2) 'dir. Buna karşılık, birleştirme sıralama aynı en kötü durum ve ortalama durum karmaşıklığına sahiptir, yani O (n log n).
- Birleştirme sıralaması, büyük veya küçük olsun, her tür veri kümesinde iyi çalışabilir. Aksine, hızlı sıralama büyük veri kümeleriyle iyi çalışamaz.
- Hızlı sıralama, küçük veri kümeleri gibi bazı durumlarda birleştirme düzeninden daha hızlıdır.
- Birleştirme sıralama yardımcı dizileri saklamak için ek bellek alanı gerektirir. Öte yandan, hızlı sıralama ek depolama için fazla alan gerektirmez.
- Birleştirme sıralama, hızlı sıralamadan daha verimlidir.
- Hızlı sıralama, sıralanacak verilerin ana bellekteki bir zamanda ayarlandığı dahili sıralama yöntemidir. Tersine, birleştirme sıralaması, sıralanacak verilerin aynı anda belleğe alınamadığı ve bazılarının yardımcı bellekte tutulması gereken harici sıralama yöntemidir.
Sonuç
Hızlı sıralama daha hızlı vakalardır ancak bazı durumlarda yetersizdir ve birleştirme türüne kıyasla çok fazla karşılaştırma yapar. Birleştirme sıralaması daha az karşılaştırma gerektirse de, hızlı sıralama O (log n) alanına ihtiyaç duyarken, ekstra diziyi depolamak için 0 (n) ek bir hafıza alanına ihtiyaç duyar.
