Sıralama algoritmalarının ilk kısmını içeren yazımda basit sıralama algoritmaları olarak Seçmeli (Selection sort) ve Eklemeli (Insertion sort) sıralama algoritmalarından bahsetmiştim. Bu yazıda gelişmiş sıralama algoritmaları olarak Birleştirmeli (Mergesort) ve Hızlı (Quicksort) sıralama algoitmalarını inceleyeceğim. Bu algoritmaları gerçeklerken hem birleştirme (merge) ve bölümleme (partition) gibi işlemler, hem de özyineleme (recursion) yaklaşımını kullanmış olacağız.
Gelişmiş sıralama algoritmaları
Gelişmiş sıralama algoritmaları hem başarımı yüksek, hem de genel yaklaşım olarak daha akıllıca yöntemler içeren algoritmalardır. Birleştirmeli Sıralama ve Hızlı Sıralama algoitmaları böl ve yönet yaklaşımının güzel birer örnekleridir. Öte yandan zaman karmaşıklıkları göz önünde bulundurulunca daha yüksek başarım, yani daha düşük karmaşıklıkla çalışırlar.
1. Birleştirmeli Sıralama
Birleştirmeli sıralama, adını sıralanmış iki diziyi birleştirerek (merge) sıralanmış bir dizi haline getirmesinden alır. Birleştirmeli sıralama, diziyi iki eşit parçaya ayırıp bu yarı dizileri kendi içinde özyinelemeli olarak sıralar ve sıralanmış dizileri birleştirir. Diziyi iki parçaya ayırıp bu parçalar üzerinde işlem yapan birleştirmeli sıralama, böl ve yönet algoritmalarının güzel bir örneğidir. Algoritmanın olumsuz bir yönü N elemanlı diziyi birleştirmek için N elemanlı ek bir dizi kullanmasıdır. Algoritmanın çalışma şeması aşağıdaki gibidir.
Algoritmanın Java dilindeki örnek kodunu aşağıda görebilirsiniz.
public class Merge {
private static Array extra;
public static void sort(Array a) {
extra = new Array[a.length];
sort(a, 0 , a.length-1);
}
private static void sort(Array a, int low, int high) {
if(high <= low) {
return;
}
int mid = low + (high - low)/2;
sort(a, low, mid);
sort(a, mid+1, high);
merge(a, low, mid, high);
}
public static void merge(Array a, int low, int mid, int high) {
int i = low;
int j = mid+1;
for(int k=low; k<=high; k++) {
extra[k] = a[k];
}
for(int k=low; k<=high; k++){
if(i > mid) {
a[k] = extra[j++];
} else if(j > high) {
a[k] = extra[i++];
} else if(extra[j] < extra[i]) {
a[k] = extra[j++];
} else {
a[k] = extra[i++];
}
}
}
}
Birleştirmeli sıralamanın karmaşıklığını hesaplamak için, özyinelemeli yaklaşıma uyan şekilde sıralanacak diziyi bir ağaç yapısına taşıyalım. Algoritma her adımda diziyi ikiye bölüp en küçük birime geldiğinde sıralayıp daha sonra sıralanmış alt dizileri birleştirerek sonuca varır. Bu diziyi Birleştirmeli sıralamaya uygun şekilde ağaç yapısına yerleştirince her bir düğüm bir alt diziyi temsil eder. Ağaç tam olarak n seviye içerir. k sayısı 0’dan n-1’e kadar ağaç seviyesini temsil etsin, yukarıdan aşağıya doğru ağacın k. seviyesinde 2k tane düğüm bulunur. Bu düğümlerin her biri 2(n-k) uzunluğunda bir alt diziyi temsil eder. Bir alt dizinin eleman sayısı 2(n-k) olduğu için en fazla 2(n-k) karşılaştırma yapılabilir. Ağacın her seviyesindeki alt dizi sayısı ve yapılabilecek en fazla karşılaştırma sayısı
2k * 2(n-k) = 2n‘dir.
n seviye ağaç için toplam n* 2n karşılaştırma yapılır.
Elde edilen n* 2n değerinin asimptotik üst sınırı O(NlgN) değeridir.
*Birleştirmeli sıralama her durumda O(nlogn) karmaşıklığında çalışacağını garanti eder.
2. Hızlı Sıralama
Hızlı sıralama, sıralanacak diziyi seçilen pivot elemana göre bölümlendirir (partition) ve bu bölümleri kendi içlerinde özyinelemeli olarak sıralar. Yine hızlı sıralama da böl ve yönet yaklaşımına güzel bir örnektir. Hızlı sıralama, kolay uygulanabilmesi, çeşitli veri tipleriyle çalıştırılabilmesi ve genel olarak hızlı çalışması sebebiyle oldukça yaygın kullanılan ünlü bir sıralama algoritmasıdır. Ortalama O(NlogN) başarımı göstermesi ve Birleştirmeli sıralamanın aksine ek alana ihtiyaç duymaması incelediğimiz dört algoritmanın içerisinde birinciliği Hızlı Sıralama’ya vermemiz için yeterlidir. Algoritmanın çalışma şeması aşağıdaki gibidir.
Algoritmanın Java dilindeki örnek kodunu aşağıda görebilirsiniz.
public class Quick {
public static void sort(Array a) {
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
}
private static void sort(Array a, int low, int high) {
if(high <= low) {
break;
}
int j = partition(a, low, high);
sort(a, low, j-1);
sort(a, j+1, high);
}
private static int partition(Array a, int low, int high) {
int i = low;
int j = high + 1;
int pivot = a[low];
while(true) {
while(a[++1] < v) {
if(i == high) {
break;
}
}
while(v < a[--j]) {
if(j == low) {
break;
}
}
if(i>=j) {
break;
}
exchange(i, j);
}
exchange(low, j);
return j;
}
}
Değerlendirme
Genel olarak basit ve gelişmiş sıralama algoritmalarını karşılaştırırsak, incelediğimiz basit sıralama algoritmaları ortalama O(N2) karmaşıklığıyla çalışıyorlarken, gelişmiş sıralama algoritmaları böl ve yönet yaklaşımına uygun özyinelemeli olarak gerçekleştirilen (daha akıllıca) ve ortalama O(NlogN) karmaşıklığıyla çalışan hızlı algoritmalardır. Aşağıda incelediğimiz dört algoritmanın zaman ve alan karmaşıklıkları karşılaştırmalı olarak gösterilmiştir.
Sıralama algoritmalarının zaman ve alan karmaşıklık değerlendirmesi.
Kaynaklar
1. Robert Sedgewick, Kevin Wayne, Algorithms 4th Edition, Addison-Wesley 2011 (chapter 2 p. 270-301).
2. http://www.sorting-algorithms.com/, en son 26.03.2015 tarihinde erişildi.
3. https://en.wikipedia.org/wiki/Merge_sort, en son 26.03.2015 tarihinde erişildi.
4. https://en.wikipedia.org/wiki/Quicksort, en son 26.03.2015 tarihinde erişildi.
5. https://en.wikipedia.org/wiki/Recursion_(computer_science), en son 26.03.2015 tarihinde erişildi.
6. https://en.wikipedia.org/wiki/Divide_and_conquer_algorithms, en son 26.03.2015 tarihinde erişildi.
