3-way partitioning

Quick-sort(hızlı sıralama) algoritmasının en büyük özelliklerinden birisi parçalama metodudur ki quicksort algoritması divide and conquer(parçala ve feth et) algoritmaları kategorisine girer.Normal parçalama işlemini yaparken eğer dizimizde birden fazla aynı değerden varsa(duplicate keys) algoritmamızı daha hızlı hale çevirmek için Djktra yeni bir yöntem geliştirmiştir.Bu duplicate değerleri dizinin ortasında toplayıp sağına ve soluna iki parça oluşturarak diziyi 3 parçaya bölme yöntemine 3-way partitioning yöntemi denir.Şu an pek lambanın parlamadığının farkındayım.Hemen nasıl yapıldığını öğrenerek lambanın parlaklığını arttıralım.

Buraya kadar bildiğimiz quicksort algoritmasındaki gibi değişimleri yaptık sadece seçtiğimiz en sağdaki duplicate key değerini atlayarak.

Ancak swap yaptığımız elemanlardan birisiseçtiğimiz duplicate değerlerden birisiyse değiştirdiğimiz yöndeki en uçtaki duplicate olmayan eleman ile yerlerini swap yapıyoruz.

Hatta iki duplitace eleman değişitirilse bile aynı işlemi onlarada uygulayarak yer değiştirebilecekleri en sağ ve en soldaki elemanlarla swap işlemi yapılır.

Görüldüğü gibi ortada çıplak gibi bir eleman kaldı bu eleman swap yapacak bir sevgili bulamayacağından artık yöntemin son basamağına geçeriz.En soldaki duplicate değerleri bu çıplak kalan elemanın soldaki elemanlarla tek tek swap yaparız en sağdaki duplicate değerleri de bu çıplak eleman dahil olmak üzere sağa doğru yönelerek değişimleri tamamlarız ve 3-way partioning yöntemimiz sonlanarak parçalama işlemimiz tamamlanmış oluyor.


sol taraftaki swaplar

sağ taraftaki son swaplar