Sıralama Algoritmaları — Bubble, Merge ve Quick Sort Karşılaştırması

Bir sıralama algoritması, aynı öğeleri küçükten büyüğe gibi belirli bir düzene sokacak şekilde yeniden düzenler. Kısa cevabı en başta isterseniz, bubble sort basittir ama büyük listeler için genelde fazla yavaştır, merge sort güvenilir $O(n \log n)$ performansı verir ve quick sort bölmeleri yeterince dengeli kaldığında pratikte çoğu zaman hızlıdır.

Doğru soru "en iyi sıralama hangisi?" değil, "hangi koşul altında en iyi?" olmalıdır. Bubble sort yerel takasları öğretir, merge sort böl-ve-yönet yaklaşımını açıkça gösterir ve quick sort en kötü durum garantisi olmadan da ortalama durum hızının neden güçlü olabildiğini gösterir.

Sıralama Algoritmaları Ne Yapar?

$[5, 1, 4, 2]$ gibi bir liste verildiğinde, algoritma aynı değerleri sıralı biçimde döndürmelidir:

$$[1, 2, 4, 5]$$

Bu kulağa basit gelir, ama farklı algoritmalar bu sonuca çok farklı yollarla ulaşır. Temel farklar şunlardır:

• öğeleri nasıl hareket ettirdikleri
• genelde kaç karşılaştırma veya takas kullandıkları
• ne kadar ek belleğe ihtiyaç duydukları
• kötü girdi düzenlerine ne kadar duyarlı oldukları

Bubble Sort: Komşu Öğeleri Tekrar Tekrar Takas Etme

Bubble sort liste boyunca ilerler ve sırası yanlış olan bitişik öğeleri takas eder. Bir tam geçişten sonra, sıralanmamış en büyük öğe sona doğru "yükselmiş" olur.

$[5, 1, 4, 2]$ üzerinde ilk geçiş şöyle görünür:

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

Ardından, artık takas gerekmeyene kadar kalan sıralanmamış bölüm üzerinde bunu tekrarlar.

Bubble sort esas olarak öğrenme amacıyla kullanışlıdır. Genel olarak zaman karmaşıklığı $O(n^2)$ olduğundan, liste büyüdükçe karşılaştırma sayısı hızla artar. Sınıftaki küçük örnekler için bu sorun değildir. Ciddi sıralama işleri içinse genelde doğru tercih değildir.

Merge Sort: Böl, Sırala, Sonra Birleştir

Merge sort böl-ve-yönet fikrini kullanır. Listeyi daha küçük parçalara ayırır, bu parçaları sıralar ve sonra sıralı parçaları yeniden birleştirir.

$[5, 1, 4, 2]$ için temiz bir görünüm şöyledir:

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

Her yarıyı sıralayın:

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

Sonra iki sıralı yarıyı birleştirin:

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

Merge sortun temel gücü öngörülebilir olmasıdır. Çalışma süresi yalnızca ortalamada değil, standart analizde de $O(n \log n)$ olur. Temel maliyet bellektir: yaygın dizi tabanlı uygulamalar birleştirme sırasında ek alan kullanır.

Quick Sort: Bir Pivot Etrafında Bölme

Quick sort da böl-ve-yönet kullanır, ama farklı bir şekilde. Bir pivot seçer, küçük öğeleri bir tarafa, büyük öğeleri diğer tarafa yerleştirir ve sonra iki tarafı özyinelemeli olarak sıralar.

$[5, 1, 4, 2]$ üzerinde pivot olarak $4$ kullanıldığında, olası bir bölme şöyledir:

$$[1, 2] \;|\; 4 \;|\; [5]$$

Artık sol ve sağ parçalar çok daha küçük olduğu için sıralama hızlıca tamamlanır.

Quick sort pratikte çoğu zaman hızlıdır çünkü birçok uygulama bölmeyi yerinde yapar ve pivot listeyi yeterince iyi böldüğünde problemi hızla küçültür. Ama bu koşul önemlidir. Pivot seçimleri tekrar tekrar kötü olursa, örneğin sürekli bir çok küçük taraf ve bir neredeyse tam dolu taraf oluşursa, en kötü durum $O(n^2)$ olur.

Bubble Sort, Merge Sort ve Quick Sort Karşılaştırması

Algoritma	Temel fikir	Tipik süre	En kötü durum süresi	Ek bellek
Bubble sort	Tekrarlanan bitişik takaslar	$O(n^2)$	$O(n^2)$	Düşük
Merge sort	Böl, yarıları sırala, birleştir	$O(n \log n)$	$O(n \log n)$	Yaygın dizi uygulamalarında daha yüksek
Quick sort	Bir pivot etrafında bölme	Çoğu zaman $O(n \log n)$	$O(n^2)$	Çoğu zaman merge sorttan daha düşük

Tek bir pratik sonuç çıkarmak isterseniz, şu olur: bubble sort bir öğretim algoritmasıdır, merge sort dengeli ve öngörülebilir seçenektir, quick sort ise uygulama pivotları iyi yönetiyorsa çoğu zaman pratik hız tercihidir.

Aynı Liste Üzerinde Çözümlü Bir Örnek

Aynı listeyi kullanın:

$$[5, 1, 4, 2]$$

Bubble sort yerel hataları düzeltmeye devam eder. Tüm yapıyı "görmez", bu yüzden birçok geçişe ihtiyaç duyabilir.

Merge sort önce problemi daha küçük sıralı parçalara ayırır, sonra bunları birleştirir. Performansının liste büyüdükçe güvenilir kalmasının nedeni bu yapıdır.

Quick sort erken aşamada güçlü bir bölme yapmaya çalışır. Bölme yeterince dengeliyse, kalan iş hızla küçülür.

Bu yüzden öğrenciler çoğu zaman bir listenin her yöntemle nasıl hareket ettiğini gördükten sonra karmaşıklık sayılarını daha iyi hatırlar. Bu sayılar rastgele etiketler değildir. Algoritmanın düzensizliği nasıl azalttığını yansıtırlar.

Sıralama Algoritmalarını Karşılaştırırken Yapılan Yaygın Hatalar

Quick Sortun Her Zaman Daha Hızlı Olduğunu Varsaymak

Quick sort pratikte çoğu zaman hızlıdır, ama her durumda en hızlı olacağı garanti değildir. Kötü pivot davranışı ona ciddi zarar verebilir.

$O(n \log n)$ Algoritmalarını Aynı Sanmak

Merge sort ve quick sort aynı ortalama büyüme oranını paylaşabilir, ama bellek kullanımı, en kötü durum garantileri veya uygulama ayrıntıları açısından aynı davranmazlar.

Kodlaması Kolay Diye Bubble Sort Kullanmak

Kodlamasının kolay olması, uygun olduğu anlamına gelmez. Çok küçük gösterimler için bubble sort uygundur. Daha büyük gerçek girdilerde ise genelde gereksiz iş yapar.

Girdi Modelini Unutmak

Bu karşılaştırmalar genelde genel girdiler üzerinde karşılaştırma tabanlı sıralamayı varsayar. Verinin özel bir yapısı varsa, counting sort gibi karşılaştırma dışı sıralamalar kararı tamamen değiştirebilir.

Her Sıralama Algoritması Ne Zaman Kullanılır?

Bubble sort çoğunlukla öğretim, adım adım izleme ve performanstan çok açıklığın önemli olduğu çok küçük örnekler için kullanılır.

Merge sort, tutarlı $O(n \log n)$ davranışının önemli olduğu ve ek belleğin kabul edilebilir olduğu durumlarda kullanılır. Uygulamaya bağlı olarak, bağlı listeler ve kararlı sıralamanın önemli olduğu durumlar için de doğal bir seçimdir.

Quick sort, pratik hızın önemli olduğu ve uygulamanın iyi bir pivot stratejisine veya yedek korumalara sahip olduğu durumlarda kullanılır. Birçok standart kütüphane sıralama stratejisi, saf bir ders kitabı sürümü yerine quick sort fikirlerini güvenlik önlemleriyle birlikte kullanır.

Farkı Hatırlamanın Hızlı Bir Yolu

Onları hareketlerine göre hatırlayın:

• bubble sort komşuları düzeltir
• merge sort sıralı yarılar oluşturur
• quick sort bir pivot etrafında böler

Bu zihinsel resim, üç isim ve üç formülü ezberlemekten daha kullanışlıdır.

Kendi Sürümünüzü Deneyin

$[7, 3, 6, 1]$ listesini alın ve bubble sort için bir geçişi, merge sort için bir bölme-ve-birleştirme döngüsünü ve quick sort için bir pivot bölmesini izleyin. Listenin her durumda neden farklı şekilde değiştiğini açıklayabiliyorsanız, kavram yerine oturmuştur.