Counting Sort

Geçenlerde bir veri işleme projesi üzerinde çalışırken dizideki sayıları en hızlı şekilde nasıl sıralayabilirim sorusuna takıldım. Aklıma hemen bildiğimiz Quick Sort ve Merge Sort gibi klasik algoritmalar geldi. Fakat bunların $O(n \log n)$ olan alt sınırına takılmak istemiyordum. Tam bu araştırma sırasında karşıma Counting Sort (Saymalı Sıralama) çıktı.

Karşılaştırma yapmadan sıralama fikri ilk başta biraz garip gelse de mantığını kavrayınca algoritmanın ne kadar zekice tasarlandığını fark ettim. Hem öğrendiklerimi pekiştirmek hem de Türkçe kaynaklara derli toplu bir not bırakmak adına bu konuyu blogda paylaşmak isted猛.

Counting Sort Nedir ve Neden Farklıdır?

Bildiğimiz sıralama algoritmalarının çoğu karşılaştırma tabanlıdır. Yani iki elemanı alır, “A sayısı B sayısından büyük mü?” diye sorar. Bu mantıkla çalışan hiçbir algoritma teorik olarak $O(n \log n)$ karmaşıklığından daha hızlı çalışamaz.

Counting Sort ise bu kuralı tamamen yıkıyor. Çünkü elemanları birbiriyle karşılaştırmıyor.

Bunun yerine dizideki her bir sayıdan kaçar tane olduğunu sayıyor ve bu frekans bilgisini kullanarak elemanların sıralı dizide durması gereken kesin konumları hesaplıyor. Bu sayede doğru koşullar sağlandığında $O(n + k)$ gibi inanılmaz bir zaman karmaşıklığına ulaşıyor.

buradaki:

$n$: Sıralanacak eleman sayısı,
$k$: Dizideki en büyük elemanın değeridir.

Algoritma Nasıl Çalışır? Step Step İnceleyelim

Counting Sort’un arkasındaki mantığı anlamak için algoritmayı 4 temel adıma bölebiliriz:

1. Maksimum Elemanı ($k$) Bulma ve Sayma Dizisi Oluşturma

İlk yapmamız gereken, girdimizdeki en büyük sayıyı bulmaktır. Diyelim ki elimizdeki en büyük sayı $k = 5$. O zaman $0$’dan $5$’e kadar olan sayıların kaçar defa geçtiğini tutabileceğimiz $k + 1$ (yani 6 elemanlı) sıfırlarla dolu bir Sayma (Counting) Dizisi oluşturuyoruz.

2. Frekansları Sayma

Orijinal diziyi baştan sona bir kez tarıyoruz. Karşılaştığımız her sayının değerini, Sayma Dizimizin indeksi olarak kullanıp oradaki değeri 1 artırıyoruz.

Örnek: Eğer dizide iki tane 3 varsa, Sayma Dizimizin 3. indeksindeki değer 2 oluyor.

3. Kümülatif Toplam (Konum Hesabı)

Şimdi Sayma Dizisi üzerinde soldan sağa doğru giderek kümülatif (toplamlı) frekansları hesaplıyoruz. Yani her elemana kendinden önceki elemanın değerini ekliyoruz.

Bu işlem bize kritik bir bilgi veriyor: Hangi sayının sıralı dizide en son hangi indekse yerleştirileceğini.

4. Nihai Diziyi Oluşturma (Kararlılık / Stability)

Son adımda orijinal diziyi sondan başa doğru taranarak elemanları kümülatif frekans dizisindeki konumlarına yerleştiriyoruz. Her yerleştirmeden sonra ilgili sayının kümülatif değerini 1 azaltıyoruz.

Küçük ama Çok Önemli Bir Detay: Orijinal diziyi neden sondan başa doğru tarıyoruz?

Cevap: Kararlılık (Stability). Bu sayede aynı değere sahip iki elemanın kendi aralarındaki orijinal sıra bozulmaz.

Ne Zaman Kullanmalı, Ne Zaman Kaçınmalı?

Counting Sort muazzam bir hız sunsa da her derde deva bir algoritma değil. Kullanırken dikkat etmek gereken durumlar var:

Ne zaman mükemmel çalışır?Sıralanacak sayıların aralığı ($k$) çok geniş değilse ve eleman sayısı ($n$) ile yakın değerlerdeyse uçarı bir performans alırsınız. Örneğin 1.000 elemanlı bir dizideki sayılar 0-100 arasındaysa Counting Sort rakipsizdir.
Ne zaman patlar?Sadece 3 elemanlı bir diziniz olduğunu varsayın: [1, 2, 1000000]. Buradaki $k$ değeri 1 milyon olduğu için algoritma sırf 3 sayıyı sıralamak adına 1 milyon elemanlı devasa bir Sayma Dizisi oluşturur. Hem bellek israfı oluşur hem de $O(n + k)$ karmaşıklığındaki $k$ yüzünden işlem süresi uzar.

Özetle

Counting Sort, karşılaştırma yapmadan sayma mantığıyla çalışan, kısıtlı aralıktaki tam sayı verilerinde hayat kurtaran harika bir algoritma. Eğer veri kümenizdeki maksimum değer kontrolden çıkmıyorsa, klasik $O(n \log n)$ sınırına takılmadan dizilerinizi ışık hızında sıralayabilirsiniz.