Go ile Algoritmalar — QuickSort

Bu gün Go ile QuickSort algoritmasını yazacağız. Bunun için harici bir kütüphaneye ihtiyacımız yok.

Kısaca QuickSort algoritmasına değinmek gerekirse bu algoritma “Böl ve Fethet” mantığı ile çalışır. Eldeki veri kümesini sürekli daha da küçülterek sonuca ulaşır. Tabiki bu yöntem tamamen dağınık listelerde çok iyi çalışırken ne yazık ki sıralanmış listelerde düşük performans verir. Sebebini anlamak için öncelikle algoritmanın mantığını iyice kavramak gerekiyor. Bunun için buyrun çalışma sürecini açıklayalım ve 10 elemanlık bir dizide deneyelim.

QuickSort algoritması verilen liste içerisinde öncelikle bir Dayanak (Pivot) belirler. Bunun için çeşitli teknikler kullanılmaktadır. Mesela 1961'de QuickSort’un ilk yayınlandığı makalede dayanak olarak ilk elemanın seçilmesi tavsiye ediliyordu. Fakat daha sonrasında bunun yerine listeden rastgele bir eleman seçilmesinin daha mantıklı olduğu ortaya çıktı. Çünkü Quicksort seçtiği dayanağa göre ikiye ayrılır. Dayanaktan küçükler ve dayanaktan büyükler. Bunu liste iki elemanlı hale gelene kadar tekrar eder. Sonra elde ettiği tüm listeleri birleştirir ve sıralanmış listeyi ortaya çıkarır. Eğer liste zaten sıralanmış ise tüm değerler dayanaktan büyük çıkar ve liste sadece 1 eleman eksik olarak ikiye ayrılır. Bu da listenin eleman kadar bölünmesi anlamına gelir. Bu olabilecek en kötü seneryodur. Bunu engellemek için de genellikle dayanak liste içinden rastgele seçilir. Ben dayanağımı şu şekilde seçeceğim.

// Dayanak Seçimi
pivot := rand.Int() % len(dizi)

Dayanağımı almak için rastgele bir sayı tuttum ve onu dizimin uzunluğuna böldüm. Böylece yukarıdaki performans kaybını minimize edeceğim.

if len(dizi) < 2 {
  return dizi
  }
left, right := 0, len(dizi)-1

Burada da gelen dizi tek elemanlı olursa fonksiyonun return etmesini sağladım. Bu kısmın amacı hatalı veri girişine engel olmak değil, fonksiyonun recursive (özyinelemeli) çalışmasını sağlamak.

Ardından dizimin uzunluğunu da kullanarak ilk ve son elemanı aldım. Bu dizimi ikiye ayırırken gerekli olacak. Bundan sonra diziyi dayanğa göre ikiye ayırıp yeniden fonksiyona sokmak gerekiyor. Bunu da basit ve kullanışlı bir for döngüsü ile yapacağız.

dizi[pivot], dizi[right] = dizi[right], dizi[pivot]

for i := range dizi {
    if dizi[i] < dizi[right] {
        dizi[left], dizi[i] = dizi[i], dizi[left]
        left++
    }
}

dizi[left], dizi[right] = dizi[right], dizi[left]

Satır satır açıklamak gerekirse:

• İlk önce seçilen dayanak ile son elemanın yerlerini değiştiriyorum.
• Sonrasında Diziyi elemanları uzunluğunda bir döngüye sokuyorum.
• Ondan sonra listenin i indexindeki sayı dayanaktan küçük ise sola atıp left değişkenimi bir arttırıyorum.
• Sonrasında dizinin son elemanı ile döngüde değeri değişen left’in yerini değiştiriyorum.

Bundan sonra yapılacak tek şey dizinin sol ve sağ taraflarını tekrardan bu döngüye sokmak.

quickSort(dizi[:left])
quickSort(dizi[left+1:])

return dizi

Bu da gayet basit.

Ve en sonunda tüm fonksiyon bu hale geliyor.

func quickSort(dizi []int) []int {
    if len(dizi) < 2 {
        return dizi
    }

    left, right := 0, len(dizi)-1

    rand.Seed(int64(len(dizi)))

    // Dayanak Seçimi
    pivot := rand.Int() % len(dizi)

    dizi[pivot], dizi[right] = dizi[right], dizi[pivot]

    for i := range dizi {
        if dizi[i] < dizi[right] {
            dizi[left], dizi[i] = dizi[i], dizi[left]
            left++
        }
    }

    dizi[left], dizi[right] = dizi[right], dizi[left]

    quickSort(dizi[:left])
    quickSort(dizi[left+1:])

    return dizi
}

Tüm kodu ve Test fonksiyonunu Github Depomda bulabilirsiniz.