Hızlı Sıralama Algoritması
Liste sıralaması problemi ön yinelemenin bir diğer uygulaması olan Hızlı Sıralama Algoritması (quick sort) uygulayalım. Burada da bir önceki sıralama probleminde olduğu gibi sıralamayı elimizdeki liste içinde, yeni bir liste yaratmadan yapalım.
Önce listeden bir isim seçerek bu isme pivot elemanı adını verelim. Amacımız pivot elemanın listedeki doğru yerini bulmak ve onu oraya koymak olsun. Pivotun doğru yerini bulmak için listeyi iki daha küçük listeye bölelim. Bu listelerden birincisi pivot elamanından önce yer alan isimler listesi olsun, ikincisi de pivottan sonra gelen elemanlar listesi olsun. Sonuç olarak, pivot elemanının doğru yeri, bu iki liste arasında yer alacaktır.
İşleme başlamak için listede bir pivot eleman seçmek gerekir. Liste hakkında hiçbir şey bilmediğimize göre en üstündeki ismi pivot elemanı olarak seçebiliriz. ikinci olarak ta listeyi iki alt listeye bölmemiz gerekir. Bunun için adına imleç(pointer) denen yeri değişebilen oklar kullanacağız. Bu oklardan birini pivot elemandan sonraki satıra ikincisini de son satıra koyalım. Geliştirdiğimiz algoritma imleçleri birbirine yaklaştırırken aşağıdaki çıkarımı(assertion) sağlasın:
Çıkarım 1:
Üsteki imlecin (A) üstünde yer alan isimler alfabetik olarak sıralamada pivot elemanından daha küçüktür. Alttaki imleçte (B) daha aşağıda yer alan isimler ise alfabetik sıralamada pivot elamanından daha büyüktür.
Yukarıdaki çıkarım, imleçlerin listede iki grup eleman gösterdiğini ifade etmektedir. Bu gruplardan üsteki imlecin üstünde yer alanlar sıralanmış olan son liste pivot elemanın önünde yer alan isimleri içerecektir. Alttaki imlecin altında yer alanlar ise pivot elemandan sonra gelen isimleri içerecektir. Şimdi de imleçleri birbirine doğru nasıl yaklaştıracağımızı aşağıdaki örnek ile gösterelim.
Örnek
Elimizde şöyle bir isim listesi olsun:
Jale, Bülent, Ali, Tolga, Canan, Banu, Gül, Ceyda, Sema, Kemal.
Bu listedeki ilk elemanı pivot eleman olarak seçer, listenin ikinci ve son elemanlarına sırası ile A ve B imleçlerini koyarak algoritmayı başlatalım.
Jale (pivot)
A Bülent
Ali
Tolga
Canan
Banu
Gül
Ceyda
Sema
B Kemal
Bir sonraki adımda B imlecini listenin yukarılarına doğru hareket ettirelim. Her seferinde de en altta kalan isimlerin pivot elemandan büyük olup olmadığını kontrol edelim. Bu adımda pivot elemandan küçük ya da ona eşit bir isme gelince, B imlecini o elamanın bulunduğu satıra yerleştiririz. İmleç en fazla pivot elemana kadar ilerleyecek ve orada duracaktır.Bu isme eriştiğimiz zaman artık B imlecini hareket ettirmekten vazgeçeriz. Yukarıdaki örnekte B imleci Ceydada duracaktır:
Jale (pivot)
A Bülent
Ali
Tolga
Canan
Banu
Gül
B Ceyda
Sema
Kemal
Şimdi de A imlecini aşağıya doğru kaydıralım. Aşağıya doğru indikçe isimleri pivot elemanı ile karlaştırarak kaydırma işlemini isimler pivot elemanından daha küçük veya ona eşit olduğu sürece devam ettirelim. Olabilecek en son şey iki imlecin birbirini geçmesidir. Bu durum ise pivot elemanın B imlecinin bulunduğu yerde olması gerektiğini gösterir. Örnekte ilk hareketler iki imleci de tıkamıştır. Bu koşullar sağlandığı zaman imleçleri hareket ettirirsek birinci çıkarımı ihlal etmiş oluruz. Yukarıdaki imleci aşağı kaydırarak listeyi şu hale getirmiş oluruz:
Jale (pivot)
Pivottan büyük yada ona eşit |
Bülent
Ali
A Tolga
Canan
Banu
Gül
B Ceyda
Pivottan büyük
isimler Sema
Kemal
Bu durumda kilit (deadlock) adı verilir. Kilidin bir şekilde açılması gerekir. Bunun yolu ise imleçlerin gösterdiği isimleri birbirleri ile değiştirmektir. Ancak bundan sonra, çıkarımızı ihlal etmeden imleçleri tekrar hareket ettirebiliriz. Bu değiştirmeden sonra yeni listemiz şöyle olacaktır:
Jale (pivot)
Bülent
Ali
A Ceyda
Canan
Banu
Gül
Tolga
Sema
Kemal
Şimdi tekrar imleçleri hareket ettirir ve her seferinde kilit oluşunca imleçlerin gösterdiği isimlerin yerlerini değiştirmeye devam ederiz. Sonunda iki imleç listenin bir yerinde birbirini kesecektir. Örneğimizde bu kesişme Gül ile Tolga arasında olacaktır. Yani; imleçlerin kesişmesi ile liste aşağıdaki hale gelecektir:
Jale (pivot)
Bülent
Ali
Ceyda
Canan
Banu
B Gül
A Tolga
Sema
Kemal
İki imleç kesişince, imleçlerin gösterdiği isimler pivot elemanına göre nasıl bir konumda olur? Bu soruya cevap verebilmek için aşağıdaki çıkarımı değerlendirmemiz gerekir.
Çıkarım 2: sıralama işleminin başında ve A imlecinin üstündeki elemanlar pivota eşit veya ondan küçük isimleri gösterir.
Yukarıdaki çıkarım sıralama işleminin başında zaten doğrudur. Her seferinde kilidi açmak için imleçler tarafından gösterilen isimlerin yerlerini değiştirdiğimiz zaman A imlecinin üstündeki isimler pivota eşit veya ondan küçük olacaktır. Demek ki, ikinci çıkarım doğrudur. B imlecinin altındaki isimler ise pivottan büyük olan isimlerdir. İki imleç kesiştiğinde, A imleci yukarıdan itibaren pivottan büyük ilk elemanı, B imleci ise aşağıdan itibaren pivottan küçük ilk elemanı göstermektir. Gerçekten de örneğimize baktığımızda; A imlecinin gösterdiği “Tolga” yukarıdan aşağıya doğru pivottan (Jale) büyük ilk eleman, B imlecicin gösterdiği “Gül” ise aşağıdan yukarıya doğru pivottan küçük ilk elemandır.
Jale (pivot)
Bülent
Ali
Ceyda
Canan
Banu
B Gül
A Tolga
Sema
Kemal
Artık pivot elemanı doğru yere yerleştirebilecek bir duruma gelmiş olduk.Yukarıdaki açıklamalardan da anlaşılacağı gibi, pivot elemanı B imlecinin gösterdiği yere girmelidir. Bu işlemi yapmanın en kestirme yolu pivot ile B imlecinin gösterdiği elemanları değiştirmektir. Bu değişimden sonra listemiz şu hale gelecektir:
Gül
Bülent
Ali
Ceyda
Canan
Banu
B jale (pivot)
A Tolga
Sema
Kemal
Bu kadar uğraşıdan sonra sadece listedeki bir elemanın yerini bulabildik! Ne var ki, biraz dikkat edilirse, bundan sonraki işin çok kolay olduğu fark edilebilir. Zira yapılması gereken iş, aynı yöntemi tekrarlayarak iki alt listeye uygulamaktır. Bu yaklaşım yapılması gereken iş miktarını iki katına çıkarmış görünse de listelerin boyları hızla kısaldığı için çabuk bitecektir.
Yukarıdaki anlatılan işlemin ard arda uygulanması ile başlangıçtaki sıralama işi herbiri en çok tek elemanlı birçok listenin sıralanmasına indirgenir.”En çok tek elemanlı” deyimi boş bir listeyi de kapsamaktadır. En çok tek elemanlı listeler doğal olarak sıralı oldukları için yukarıdaki yöntemin tekrarlı uygulaması ile elimizdeki liste sıraya dizilmiş olur.
Şimdi de Hızlı Sıralama Algoritmasını bir sözde-kod ile sunalım. Bu işlemi Sırala adı verilen bir yordam ile çağıralım. Bu yordamın ilk işi listenin uzunluğunu ölçmektir. Eğer, listede iki veya daha fazla isim varsa yordam, if-then-else yapısının esle kısmına dallanarak devam eder. Aksi halde listeyi sıralanmış kabul ederek dişi bitirir. Listede iki ya da daha fazla isim varsa, pivot elemanını seçtikten sonra pivot elemanının altındaki ve üstündeki liste için sıralama yordamını tekrar çağırır.Bu istek, sırala yordamının soniki satırında ek uygulama olarak belirir.Şekil 5.15’te Sıralama yordamının sözde-kodu verilmektedir.
Procedure Sırala(Liste)
İf(Liste ikiden az eleman içeriyorsa)
Then(Listeyi sırala olarak belirle)
Else (Listenin ilk elamanını pivot elemanı olarak seç
A imlecini listenin ikinci ve B imlecini de son elemanına yerleştir
While (A ve B imleçleri kesişmediği sürece) do
[B imlecini yukarı doğru pivottan küçük veya ona eşit olan elemana
kadar kaydır;
A imlecini aşağı doğru pivottan büyük olan elemana kadar kaydır)
İf (A ve B imleçleri kesişmiyorsa)
Then(imleçlerin gösterdiği yerlerin elemanlarını değiştir)]
B imlecinin gösterdiği eleman ile pivot elemanın yerini değiştir.
Sırala yordamını pivotun üstündeki listeye uygula
Sırala yordamını pivot elemanının altındaki listeye uygula.
Şekil 5.15: Hızlı Sıralama yordamı
Aşağıdaki örnek ile Hızlı Sıralama algoritmasının nasıl çalıştığını daha iyi anlamaya çalışalım:
Örnek
Elimizde şöyle bir liste olsun:
Bülent Emine Dilek Ali Cemal
Listenin uzunluğuna bakarak iki elemandan fazla olduğunu görürüz.Pivot eleman olarak Bülent’i seçeriz ve imleçleri listenin ikinci ve en alt elemanlarını gösterecek şekilde yerleştiririz..
Bülent (pivot eleman)
A→ Emine
Dilek
Ali
B → Cemal
Önce b imlecini Ali’ye kaydırırız. Aimleci ise Emre’den aşağı inmez .Ali ile Emine’nin yerlerini değiştirirsek listemiz şu hale gelir:
Bülent (pivot eleman)
A→ Ali
Dilek
B→ Emine
Cemal
Bu durumda, A imlecini Dilek’e ,B imlecini Ali’ye kadar kaydırabiliriz ve Ali ile Bülent’in yerlerini değiştiririz. Listemiz şu durma gelir:
Ali
A → Bülent(pivot eleman)
B→ Dilek
Emine
Cemal
Şimdi pivot elemanın altındaki ve üstündeki listeleri sıralamak isteriz.Pivot elemanın üstündeki liste tek elemandan oluştuğu için zaten sıralı demektir.Dikkat edilirse bu sırada algoritmamızda iki aktivasyon bulunmaktadır.Bu aktivasyonlardan birisi
Sırala yordamını pivotun üstündeki listeye uygula
komutunu çağırır ve beklemeye başlar.Bu sırada, yukarıda verilen komut ise, içinde Ali bulunan listeyi sıraya dizmek ile uğraşır.Bu durum şekil 5.16’da göstermek için ikinci aktivasyon uzun sürmez.Listedeki elemanların sayısına bakar bakmaz tek eleman olduğunu görür ve işini başarı ile sonlandırır.Algoritma bu aşamada ikinci aktivasyonu sonlandırarak ilk aktivasyona geri döner.O sırada da ilk aktivasyon
Sırala yordamını pivotun altındaki listeye uygula
Komutu ile tekrar ikinci bir aktivasyon başlatıp bekleme durumuna geçer.Bu ikinci aktivasyon pivot elemanın altındaki;
Dilek
Emine
Cemal
listesini sıraya koymak için sıralama yordamını başlatır. İlk iş olarak Dilek ismini pivot elemanı olarak seçer.Emine ve Cemal isimlerini birer imleç ile gösterir.Cemal’deki imleci yukarı Emine’deki imleci aşağı doğru kaydırmaz.Kilidi açmak için Cemal ile Emine’nin yerlerini değiştirir.İmleçleri kaydırdıktan sonra B imlecinin gösterdiği Cemal ile Dilek’in yerlerini değiştirir.Bu aktivasyon şöyle bir liste üretir
Cemal
Dilek (pivot eleman)
Emine
ve
Sırala yordamını pivotun üstündeki listeye uygula
komutu ile yeni bir aktivasyon başlatır.Bu aktivasyon, içinde Cemal ismi Başlangıç aktivasyonunu listenin alt kısmını sıralamak için yeni bir aktivasyon çağırıp beklemeye koyulmuştur.İkinci aktivasyon ise pivot elemanının üstündeki liste sıraya dizilsin diye üçüncü bir aktivasyon çağırıp beklemeye koyulmuştur.Tek isimli listeler zaten sıralı oldukları için üçüncü aktivasyon listenin sıralı olduğunu bildirir ve görevini hemen bitirir.
Bu anda beklemede olan ikinci aktivasyon
Sırala yordamını pivotun altındaki listeye uygula
komutu ile içinde Emine ismi bulunan listeye sıralamak için üçüncü bir aktivasyon başlatır.Bu aktivasyon da işini hemen bitirir ve işi yine ikinci aktivasyona bırakır.İkinci aktivasyon da işini hemen bitirerek işi başlangıç aktivasyonuna bırakır.bu sırada başlangıç aktivasyonu en son komutu olan
Sırala yordamını pivotun altındaki listeye uygula
Komutunu vermiş beklemektedir. İş başarı ile sonlandığından başlangıç aktivasyonu da işini bitirmiş olur ve durur.İşte bu noktada tüm liste artık sıraya dizilmiştir.