İçerik

• Karşılaştırma Tablosu
• Quick Sort'un tanımı
• Merge Sort'un tanımı
• Sonuç

Hızlı sıralama ve birleştirme sıralama algoritmaları, benzer şekilde çalışan bölme ve fethetme algoritmasına dayanır. Hızlı ve birleştirme sıralaması arasındaki önceki fark, hızlı sıralamada pivot öğesinin sıralama için kullanılmasıdır. Öte yandan, birleştirme sıralaması, sıralama işlemini gerçekleştirmek için pivot öğesini kullanmaz.

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.

1. 1. Karşılaştırma Tablosu
   2. Tanım
   3. Anahtar Farklılıklar
   4. Sonuç

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 olarak da bilinir bölüm değişimi. Elemanları bölümlemek için bir anahtar elemanı (eksen olarak da 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, dizilmesi gereken n sayısının A, A, A, …… .., A dizisi olduğunu varsayalım. Hızlı sıralama algoritması, aşağıdaki adımlardan oluşur.

1. İlk eleman veya anahtar olarak seçilen herhangi bir rastgele eleman, = A (1) anahtarını varsayar.
2. “Low” işaretçisi ikinciye yerleştirilir ve “yukarı” işaretçisi dizinin son elemanına yerleştirilir, yani low = 2 ve yukarı = n;
3. Tutarlı bir şekilde, “düşük” işaretçiyi (A> tuşu) kadar bir konum kadar artırın.
4. Sürekli olarak, “yukarı” işaretçisini (A <= tuşu) olana kadar bir konum kadar azaltın.
5. Eğer yukarı, A ile A arasındaki düşük kavşak A'dan büyükse.
6. 5. ve 5. adımları, 5. adımdaki koşul başarısız olana kadar (yani yukarı <= düşük) tekrarlayın, ardından A ile anahtar değişimi yapın.
7. 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.
8. 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. Ancak, karmaşık ve çok özyinelemelidir, bu nedenle büyük diziler için uygun değildir.

Merge Sort'un tanımı

Birleştirme sıralaması Aynı zamanda böl ve yönet 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ıralama, her iki yarının depolanması için iki öğenin kullanıldığı üç 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, A, ………, A şeklinde sıralanacak n sayısı olan bir dizi dizisi olsun. Birleştirme sırası verilen adımları izler.

1. A dizisini yaklaşık n / 2 olarak sıralanmış alt diziye 2'ye bölün. Bu, (A, A), (A, A), (A, A), (A, A) alt dizilerindeki öğelerin sıralı olmak.
2. 4 boyutunda sıralanmış alt dizilerin listesini elde etmek için her çift çiftini birleştirin; alt dizilerdeki elemanlar da (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A) şeklinde sıralanır.
3. 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 setleriyle bile iyi çalışır. Ancak, belleğin daha büyük bir bölümünü tüketir.

1. 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.
2. Hızlı sıralama en kötü durumda karmaşıklığı O (n²) En kötü durumda çok daha fazla karşılaştırmalar alır gibi. 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).
3. 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.
4. Hızlı sıralama, küçük veri kümeleri gibi bazı durumlarda birleştirme düzeninden daha hızlıdır.
5. Birleştirme sıralaması, yardımcı dizileri depolamak için ek bellek alanı gerektirir. Öte yandan, hızlı sıralama ek depolama için fazla alan gerektirmez.
6. Birleştirme sıralama, hızlı sıralamadan daha etkilidir.
7. 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 verimsizdir ve ayrıca birleştirme sıralamasına göre ç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.