Sıralama Algoritmaları: Merge, Quick, Heap Nedir?

Bilgisayar mühendisliğinde veri yapıları ve algoritmalar dersinin temel konularından olan sıralama algoritmaları, veriyi belirli bir düzene sokmak için kullanılır. Merge Sort, Quick Sort ve Heap Sort, verimlilikleri ve farklı çalışma prensipleriyle öne çıkan popüler algoritmalardır.

Kısa cevap

Merge Sort, veriyi bölerek sıralayan 'divide and conquer' prensibini kullanır; Quick Sort, pivot seçimiyle veriyi bölümleyen ve özyinelemeli çalışan bir algoritmadır; Heap Sort ise yığın (heap) veri yapısını kullanarak sıralama yapar.

Adım adım çözümlü örnekler

Merge Sort ile [38, 27, 43, 3, 9, 82, 10] dizisini sıralayın.

1. Diziyi sürekli ikiye bölerek tek elemanlı alt dizilere ayırın.
2. Tek elemanlı alt dizileri birleştirirken sıralı bir şekilde birleştirin.
3. Tüm dizi birleşene kadar bu işleme devam edin. Sonuç: [3, 9, 10, 27, 38, 43, 82]

Quick Sort ile [10, 7, 8, 9, 1, 5] dizisini sıralayın. Pivot olarak son elemanı seçelim.

1. Dizinin son elemanını (5) pivot olarak seçin.
2. Diziyi pivot'tan küçükler ve büyükler olarak ikiye ayırın: [1, 5, 8, 9, 7, 10]
3. Pivot'un solundaki [1] ve sağındaki [8, 9, 7, 10] alt dizileri için aynı işlemi özyinelemeli olarak uygulayın.
4. Tüm alt diziler sıralandığında birleştirin. Sonuç: [1, 5, 7, 8, 9, 10]

Heap Sort ile [4, 10, 3, 5, 1] dizisini sıralayın.

1. Diziyi bir max-heap yapısına dönüştürün: [10, 5, 3, 4, 1]
2. En büyük elemanı (heap'in kökü, 10) dizinin sonuna taşıyın ve heap'ten çıkarın. Dizinin boyutu 1 azaltılır.
3. Kalan elemanlarla tekrar heap özelliğini sağlayın ve en büyük elemanı (5) bir önceki elemanın yanına taşıyın.
4. Tüm elemanlar sıralanana kadar tekrarlayın. Sonuç: [1, 3, 4, 5, 10]

Bilgi kartları

Mini test

S1.Aşağıdakilerden hangisi 'divide and conquer' stratejisini kullanır?

Doğru cevap: C. Merge Sort, problemi alt problemlere bölerek çözen bir 'divide and conquer' algoritmasıdır.

S2.Quick Sort'un en kötü durum zaman karmaşıklığı nedir?

Doğru cevap: C. Quick Sort'ta pivot seçimi kötü yapıldığında (her zaman en küçük veya en büyük eleman seçildiğinde) zaman karmaşıklığı O(n^2) olur.

S3.Merge Sort'un ekstra bellek ihtiyacı genellikle nasıldır?

Doğru cevap: B. Merge Sort, birleştirme işlemi sırasında geçici olarak orijinal dizi kadar (O(n)) ek bellek alanına ihtiyaç duyar.

📄Bu konuyu PDF çalışma kağıdı olarak indirKonu özeti + 10 soru + cevap anahtarı — sınıfta paylaş, yazdır.↓

Sık yapılan hatalar

✗

Quick Sort her zaman Merge Sort'tan daha hızlıdır. — Doğrusu: Quick Sort'un ortalama performansı Merge Sort'a yakın olsa da, en kötü durum performansı O(n^2) olabilirken Merge Sort'un her zaman O(n log n)'dir. Ayrıca Merge Sort'un sabit bellek ihtiyacı yoktur.

✗

Heap Sort, sıralama yaparken diziyi yerinde değiştirmez. — Doğrusu: Heap Sort, yığın yapısını kullanarak diziyi genellikle yerinde (in-place) sıralayabilir, ek bellek ihtiyacı düşüktür.

Sıkça sorulan sorular

Bu üç sıralama algoritması arasındaki temel farklar nelerdir?

Merge Sort böl ve fethet prensibiyle çalışır ve kararlı bir algoritmadır. Quick Sort, pivot seçimiyle veriyi bölümleyerek özyinelemeli çalışır ve genellikle yerinde sıralama yapar. Heap Sort ise yığın veri yapısını kullanarak en büyük/en küçük elemanı hızla bulur ve sıralar.

Hangi sıralama algoritması ne zaman tercih edilmelidir?

Büyük veri kümeleri ve kararlılığın önemli olduğu durumlarda Merge Sort tercih edilebilir. En iyi ortalama performansı ve yerinde sıralama avantajı nedeniyle Quick Sort sıkça kullanılır. Heap Sort ise bellek kısıtlaması olan durumlarda iyi bir seçenektir.

Bu algoritmaların kararlılık (stability) durumu nedir?

Merge Sort kararlı bir sıralama algoritmasıdır (eşit elemanların göreceli sırasını korur). Quick Sort ve Heap Sort genellikle kararlı değildir.

İlgili konular