Best Average Worst
Ω(n log(n)) θ(n log(n)) O(n^2)
Aşağıdaki gibi bir array'imiz olsun. Array'in en ortadaki elemanını pivot olarak belirleriz. Pivotta küçük olan sayılar pivot'un soluna gelecek, pivottan büyük sayılar pivotun sağına gelecek şekilde düzenleriz. Bunu da şöyle yaparız:
Array'i başından ve sonundan itibaren taramaya başlarız.Soldan tarayıp pivottan büyük bir eleman bulur ve sağdan tarayıp pivottan küçük bir eleman bulur, birbirleriyle swap ederiz. Pivota eşit sayıları ise sağa ya da sola taşıyabiliriz. Array'imizin pivottan küçük olanlar ve pivottan büyük olanlar ayrılma işlemi tamamlandığında , aynı şeyi bu array'lere(yani pivottan küçük olanların oluşturduğu array'a ve pivottan büyük olanların oluşturduğu array'a) de uygularız.Bunu tek elemanlı array'lere indirgeyene kadar yaparız.
Array'in soldan taramaya başlayalım.
Soldan tararkenki amacımız pivottan büyük bir sayı bulmak ,
Sağdan tararkenki amacımız pivottan küçük bir sayı bulmak,
Ve nihayetinde bu iki sayıyı swap edelim.
6<9 olduğu için taramaya devam et.
14>9 olduğu için a[1] indisini kenara al ve bununla hangi sayıyı swap yapacağımızı bulmak için sağdan taramaya başla.
1<9 olduğu için a[9] elemanını da kenara al . a[1] ve a[9] 'u swap et.
Kaldığımız yerden taramaya devam edelim.
-3<9 olduğu için taramaya devam et.
24>9 olduğu için a[3] indisini kenara al ve bununla hangi sayıyı swap yapacağımızı bulmak için sağdan taramaya başla.
5<9 olduğu için a[8] elemanını da kenara al. a[3] ve a[8] 'i swap et.
Kaldığımız yerden taramaya devam edelim.
Soldaki taramamızda pivotun üzerine geldik. a[4] 'ü kenara al ve bununla hangi sayıyı swap yapacağımızı(öyle bir sayı varsa ) bulmak için sağdan taramaya başla.
8<9 olduğu için a[6] elemanını da kenara al. a[4] ve a[6] 'i swap et.
Kaldığımız yerden taramaya devam edelim.
Soldan taramamıza devam ediyoruz..a[5]>a[6]
Sağdaki tarama işleminde ise pivotun üzerinde olduğumuz için beklemedeyiz. Dolayısıyla a[6] elemanını da kenara al. a[5] ve a[6] 'yı swap et.
Kaldığımız yerden taramaya devam edelim.
Her iki taraftan yaptığımız taramada da pivota ulaştığımız için tarama işlemi tamamlandı ve seçtiğimiz pivotun(9'dan) soluna pivottan küçük sayıların , sağına da pivottan büyük sayıları getirmiş olduk.
Şimdi de önce pivottan küçük sayılara sonra pivottan büyük sayılara quick sort algoritmasını uygulayalım.
Pivot olarak -3'ü seçelim.
Pivot olarak 24'ü seçelim.
Quick sort algoritmasını elimizdeki array'leri parçalayarak (yukarıda olduğu gibi) recursive olarak, tek elemanlı array'lere ulaşana kadar uygularız. Recursion durduğu anda array'imizi sıralı hale getirmişizdir.
Hiç yorum yok:
Yorum Gönder