Öncelikle elimizde bir dizi olsun.
Dizi elemanlarının içinden öncelikle bir pivot eleman seçeriz. Bu seçtiğimiz pivot diğerleriyle karşılaştıracağımız bir eleman olacaktır. Pivot elemanını istediğimiz yerden seçebiliriz. Ben pivot eleman olarak en sağda bulunan 5 elemanını seçiyorum. Seçilmiş olan pivot elemanı ortaya alalım ve bu pivot elemana göre küçük olanlar sol tarafa yazılır. Büyük olan elemanlar ise pivot elemanın sağ tarafına yazılır.
Aynı algoritma bölünmüş gruplar için tekrar yapılır. Bölünmüş gruplar için tekrar pivot eleman seçilir ve işlemler tekrar yapılır.
Pivot elemanı ortaya alalım ve pivot elemana göre göre tekrar tekrar sıralama işlemi yapalım.
Her bir grup için sıralama işlemi yaptıktan sonra hepsini birleştiririz. Soldan sağa doğru yazdığımız zaman bütün elemanlar sıralanmış olur.
Algoritmanın Karmaşıklığı
Her satırdaki her elemena bakar eğer n tane sayı varsa n tane sayıya bakıyor olacağız.Algoritmanın adım sayısı dersek logn tanedir. Buradaki log iki tabanında demektir. Problem her seferinde 2 parçaya bölünür.100 sayı var diye düşünelim log iki tabanında 100 sayısını yukarı yuvarlama işlemi sonucunda 7 elde edilir. Buradan çıkaracağımız sonuç algoritmanın sıralanması 7 adımda gerçekleşmektedir.
Algoritmanın performansı iyi bir durumda nlogn'dir.
Her zaman nlogn ile karşılaşmayız. Tesadüfen bütün elemanlar pivottan küçük olsun böyle bir durumda biz elemnları iki parçaya bölemeyiz. En sondaki pivotu bırakıp hem bir solundaki elemanı pivot seçeriz. Böyle bir durumda n-1 tane sayı olacaktır. Yeni dizi için yeniden pivot seçeriz ve bu işlemleri tekrar tekrar yapmak zorunda kalırız.
Bu durumda algoritmanın en kötü durum karmaşıklığı n^2 olur. Genel olarak Quick Sort algoritmasında ise ortalama durum nlogn'dir.
Hiç yorum yok:
Yorum Gönder