Mühendislik ve Teknoloji

Quicksort Yani Hızlı Sıralama Algoritmasını Kolayca Anlayalım!

Çevrimiçi alışverişlerinizde bir şeyler satın alırken, genellikle aradığınız ürünleri fiyat, ortalama müşteri memnuniyet puanı veya belki de tarihe göre sipariş etme seçeneğine sahip olursunuz. Düşünürseniz alışveriş yaptığınız ortamda binlerce ürün vardır. Oysa ki bir sürü şeyi (örneğin rafınızdaki kitaplar) düzene koymayı denediyseniz, bunun zaman alacağını bilirsiniz. Bu nedenle dünya bir sıralama algoritması olan Quicksort’u icat ettiği için bilgisayar bilimcisi Tony Hoare’ye büyük bir şükran borçludur.

İşin ilginç olanı Hoare, Quicksort algoritmasını çevrimiçi alışveriş yapmayı düşünmeden, bu tip bir alışverişin henüz daha farkında olmadığımız zamanlarda geliştirdi. Ancak yine de onun geliştirdiği bu algoritma günümüzün en iyi sıralama algoritmalarından biri olarak kabul ediliyor. Bunun sonucunda da günümüzde bir çok alana uygulanıyor. 

Quicksort Algoritması Başlangıçta Bubble Sort Yani Kabarcık Sıralaması İdi

Kabarcık Sıralaması, bilgisayar bilimlerinde kullanılan yalın bir sıralama algoritmasıdır. Sıralanacak dizinin üzerinde sürekli ilerlerken her defasında iki öğenin birbiriyle karşılaştırılıp, karşılaştırılan öğelerin yanlış sırada olmaları durumunda yerlerinin değiştirilmesi mantığına dayanır.

Kabarcık sıralaması adını, tıpkı baloncukların yüzeye çıkması gibi listenizdeki şeylerin yavaş yavaş doğru yerlerine doğru hareket etmesinden alır. Arkasındaki fikir basittir. Size bir sıraya konması gereken (örneğin sayılar) bir liste verildiğinde (örneğin artan), önce ilk iki öğeyi karşılaştırır ve doğru sırada değilse bunları değiştirirsiniz. Şimdi sahip olduğunuz listede, ikinci ve üçüncü şeye bakar ve yanlış sıradaysa bunları değiştirirsiniz. Listenizin sonuna ulaşana kadar listede üçüncü ve dördüncü sırada, listede dördüncü ve beşinci sıradakileri aynı biçimde değiştirmeye devam edersiniz.

Bu işlem sırasında hiçbir şeyi değiştirmek zorunda kalmadıysanız bu, listenin zaten doğru sırada olduğu anlamına gelir. Bunun sonucunda da durursunuz. Ancak en az bir çifti değiştirmek zorunda kaldıysanız, aynı işlemi listenin başından itibaren yeniden başlatırsınız. Sonunda listeniz sıralanacaktır.

Sizin de fark edeceğiniz gibi bubble sort algoritması basit ama çok da etkili değildir. Sizin ( daha doğrusu algoritmanın çalıştığı bilgisayarın) bir listenin tamamının sıralanması için gereken sıra listenin uzunluğu ile ilişkilidir. Tony Hoare’nın işin içine girdiği yerde burası olacaktır. Bubble Sort algoritmasını daha verimli kılmak için yaptığı çalışmalar sonucunda, Quicksort algoritması doğacaktı.

Quicksort Yani Hızlı Sıralama Algoritması Nasıl Çalışır?

Bu algoritma, kabarcıkla sıralaması kadar basit olmasa da arka planındaki fikir güzel ve zariftir. Diyelim ki elimizde artan biçimde sıraya konması gereken bir sayılar listesi var. Böyle bir sayı listesi verildiğinde, önce listenizden bir sayı seçersiniz. Buna pivot sayı denir. Sonrasında da listedeki diğer tüm sayıları bu sayıyla karşılaştırırsınız.

Genel fikir, tüm sayıları kontrol etmek ve pivottan daha küçüklerse, artan sırada dizdiğimiz için, pivotun önüne taşımaktır. Aşağıdaki örnekte pivot sayımız yedidir. Bu mantıkla düzenledikten sonra yedi sayısının sol tarafındakiler daha küçük, sağ tarafındakiler ise daha büyük olacaktır.

Ancak sizin de fark ettiğiniz gibi sayılar hala düzenli değil. Bu durumda, aynı işlemi listenin daha küçük kısmına ve daha büyük kısmına ayrı ayrı uygulamanız gerekecektir. Yani önce yediden küçükler için bir pivot sayı seçersiniz ve ona göre sıralarsınız. Sonrasında da aynı işlemi yediden büyükler için de yaparsınız. Aşağıdaki örnekte bunun için 4 ve 9 seçilmiştir. Bu işlemin sonucunda sayı diziniz sıralanmış olur.

Hoare’nin Hızlı Sıralama Algoritması İçin Harika Fikri

Ancak bilgisayar konusunda deneyimliyseniz, bu sıralamanın aslında küçükler ve büyükler biçiminde iki liste oluşturduğunuz ve bir bilgisayarın çalışma verimliliğini düşürdüğünü fark edeceksiniz. Bunun için bu bölünmeyi ek listelere ihtiyaç duymadan yapmak gerekir. Hoare’nin bunun için harika bir fikri vardı.

Yine bir sayı dizisi düşünün ve bir sayıyı pivot olarak seçin. Şimdi sol işaret parmağınızı pivotun sağındaki sayıya (ikinci sayı) ve sağ işaret parmağınızı son sayıya koyduğunuzu hayal edin. Amacınız pivota göre yanlış sırada olan sayı çiftlerini bulmak ve listeyi hem soldan hem de sağdan tarayarak yerlerini değiştirmektir.

Şimdi aşağıdaki görsele balın. L harfi sol, R harfi de sağ işaret parmağınızı gösteriyor. Bu aşamada pivot sayımızdan yani 7 sayısından, daha büyük sayıları arıyoruz. Sol taraftaki sayı yani 4, pivot sayımız yani 7’den küçük. Bu durumda sol parmağınızı bir sayı sağa doğru kaydırın. Şimdi 6 sayısındasınız. Yine küçük. Bir kere daha sağa kaydırın. Bir sonraki sayı ise 9. Şimdi durun.

Sırada sağ parmağınız var. Buradaki sayı 10. Pivot sayımız olan 7’den daha küçük olanlara bakalım. 10 sayısı olmadı, bu durumda parmağınızı bir sayı sola kaydırın ve 3 sayısın da durun. Her iki parmağınız durduğunda, pivota göre yanlış sırada olan iki sayı belirlediniz. Şimdi bu sayıların yani 3 ile 9 sayısının yerlerini değiştirin.

Bu işlemin birkaç tekrarından sonra her iki parmak da durduğunda sıralamamız tamamlanır. Pivot, listedeki en küçük veya en büyük sayı olduğunda, tanımladığımız algoritmanın başının belaya girebileceğini unutmamalıyız. Ancak bununla başa çıkmanın da yolları vardır. Ayrıntılar için Wikipedia’ya bakın.

Bu yazımızda en basit hali ile Quicksort yani Hızlı Sıralama algoritmasının çalışma mantığını aktardık. Elbette konu hakkında bilginizi geliştirmek için ek kaynaklardan öğrenmeye devam etmeniz gerekecektir. Bunun için aşağıdaki kaynaklar kısmımıza göz atabilirsiniz.



Kaynaklar ve ileri okumalar


Dip Not:

Matematiksel, 2015 yılından beri yayında olan ve Türkiye’de matematiğe karşı duyulan önyargıyı azaltmak ve ilgiyi arttırmak amacıyla kurulmuş bir platformdur. Sitemizde, öncelikli olarak matematik ile ilgili yazılar yer almaktadır. Ancak bilimin bütünsel yapısı itibari ile diğer bilim dalları ile ilgili konular da ilerleyen yıllarda sitemize dahil edilmiştir. Bu sitenin tek kazancı sizlere göstermek zorunda kaldığımız reklamlardır. Yüksek okunurluk düzeyine sahip bir web sitesi barındırmak ne yazık ki günümüzde oldukça masraflıdır. Bu konuda bizi anlayacağınızı umuyoruz. Ayrıca yazımızı paylaşarak da büyümemize destek olabilirsiniz. Matematik ile kalalım, bilim ile kalalım.

Matematiksel

Bir cevap yazın

E-posta hesabınız yayımlanmayacak.

Başa dön tuşu