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.

 

Bir cevap yazın

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Close
Join me: