10. Sınıf Tema 5: Sayma, Algoritma ve Bilişim Test 2

Bir bilgisayar programı, \( n \) elemanlı bir listeyi sıralamak için her adımda listeyi ikiye bölerek çalışan bir algoritma kullanmaktadır. Bu algoritmanın zaman karmaşıklığı \( O(\log n) \) olarak verilmiştir.
Bu bilgiye göre, bu algoritma aşağıdaki sıralama algoritmalarından hangisi olabilir?

A) Kabarcık Sıralama (Bubble Sort)
B) Birleştirme Sıralama (Merge Sort)
C) Hızlı Sıralama (Quick Sort)
D) Araya Sokma Sıralama (Insertion Sort)

Bu soruyu çözmek için, verilen algoritma özelliklerini ve seçeneklerdeki sıralama algoritmalarının temel çalışma prensiplerini ve zaman karmaşıklıklarını incelememiz gerekiyor.

• Algoritmanın Özellikleri: Bir bilgisayar programı, $n$ elemanlı bir listeyi sıralamak için her adımda listeyi ikiye bölerek çalışan bir algoritma kullanmaktadır. Bu algoritmanın zaman karmaşıklığı $O(\log n)$ olarak verilmiştir.
• Sıralama Algoritmalarının İncelenmesi: Şimdi seçeneklerdeki algoritmaların özelliklerine bakalım:
• A) Kabarcık Sıralama (Bubble Sort): Bu algoritma, listenin başından sonuna doğru ardışık elemanları karşılaştırır ve yanlış sıradaysa yerlerini değiştirir. Bu işlem, liste tamamen sıralanana kadar tekrarlanır. Listeyi ikiye bölme prensibiyle çalışmaz. Ortalama ve en kötü durum zaman karmaşıklığı $O(n^2)$'dir.
• B) Birleştirme Sıralama (Merge Sort): Bu algoritma, "böl ve yönet" (divide and conquer) prensibine dayanır. Listeyi özyinelemeli (recursive) olarak iki eşit parçaya böler, bu parçalar tek elemanlı hale gelene kadar devam eder. Daha sonra bu tek elemanlı listeleri sıralı bir şekilde birleştirerek orijinal listeyi sıralar. Listenin her adımda ikiye bölünmesi, bu algoritmanın temel özelliğidir. Bu bölme işlemi, $\log n$ seviye derinliğinde gerçekleşir. Önemli Not: Birleştirme Sıralama'nın genel zaman karmaşıklığı $O(n \log n)$'dir. Soruda belirtilen $O(\log n)$ karmaşıklığı, genellikle bir sıralama algoritmasının toplam karmaşıklığı için değil, ikili arama gibi algoritmalar veya bir bölme işleminin derinliği için geçerlidir. Ancak, seçenekler arasında "her adımda listeyi ikiye bölme" özelliğine en uygun algoritma Birleştirme Sıralama'dır. Sorudaki $O(\log n)$ ifadesi, algoritmanın bölme aşamasının logaritmik doğasına veya sorunun basitleştirilmiş bir ifadesine işaret ediyor olabilir.
• C) Hızlı Sıralama (Quick Sort): Bu da bir "böl ve yönet" algoritmasıdır. Bir pivot eleman seçer ve listeyi bu pivot etrafında iki alt listeye ayırır (pivot'tan küçükler ve pivot'tan büyükler). Daha sonra bu alt listeleri özyinelemeli olarak sıralar. Her adımda listeyi *eşit* ikiye bölme garantisi yoktur; bölme oranı pivot seçimine bağlıdır. Ortalama zaman karmaşıklığı $O(n \log n)$, en kötü durum zaman karmaşıklığı ise $O(n^2)$'dir.
• D) Araya Sokma Sıralama (Insertion Sort): Bu algoritma, listeyi baştan sona tarar ve her elemanı, daha önce sıralanmış olan kısmın doğru yerine yerleştirir. Listeyi ikiye bölme prensibiyle çalışmaz. Ortalama ve en kötü durum zaman karmaşıklığı $O(n^2)$'dir.
• Sonuç: Verilen algoritma tanımında "her adımda listeyi ikiye bölerek çalışan" ifadesi, Birleştirme Sıralama (Merge Sort) algoritmasının en belirgin özelliğidir. Her ne kadar Birleştirme Sıralama'nın toplam zaman karmaşıklığı $O(n \log n)$ olsa da, listeyi ikiye bölme mekanizması logaritmik bir derinliğe sahiptir ve bu özellik onu diğer seçeneklerden ayırır.

Cevap B seçeneğidir.