Siralama algoritmalari, verilerimizin sirali bir sekilde olmasini saglayabilmek için kullandigimiz yöntemlerdir.
Peki verilerimizin sirali olmasinin önemi nedir?
Arama yaparken Binary Search algoritmasi ile sirali verilerde çok hizli arama gerçeklestirebiliriz. Daha farkli bir örnek vermek gerekirse en en kisa yol hesabi için de verilerin sirali bir sekilde bulunmasi gerekmektedir. Bu ve bunun gibi birçok sebebe dayanarak verilerimizin sirali bir sekilde tutumasinin faydali olacagini söyleyebiliriz.
Bu makalede siralama algoritmalarindan Quick Sort algoritmasini inceleyecegiz.
Kisaca, bu algoritma diziler ile islem yapmaktadir. Dizinin ortasindaki sayiyi bulur ve bu sayiyi baz alarak diger sayilari bu sayidan küçük ya da büyük diyerek böler. Sonuçta ortaya çikan gruplar için ayni islem tekrarlanir. Bu yönteme divide and conquer yaklasimi da denmektedir.
Sayisal bir örnek verelim:
sayilar = {9, 4, 6, 7, 3, 8, 1}
1. Dizinin ortasindaki sayi bulunur. sayilar[3] = 7
2. Seçilen elemani dizideki elemanlarla karsilastirarak büyük ve küçükleri gruplandir 3 1 4 6 (7) 9 8
3. Küçük elemanlarin ortasinidaki sayi bulunur. sayilar[2] = 1
4. Seçilen elemani dizideki elemanlarla karsilastirarak büyük ve küçükleri gruplandir (1) 3 4 6
5. Büyük elemanlarin ortasindaki sayi bulunur. sayilar[1] = 9
6. Seçilen elemani dizideki elemanlarla karsilastirarak büyük ve küçükleri gruplandir 8 (9)
7. 4.maddedeki büyük elemanlarin ortasindaki sayi bulunur. sayilar[1] = 4
8. Seçilen elemani dizideki elemanlarla karsilastirarak büyük ve küçükleri gruplandir 3 (4) 6
9. Birlestirme islemine geçilir. Önce son grup birlestirilir:
3 4 6
1 3 4 6
1 3 4 6 7
1 3 4 6 7 8 9
seklinde siralama islemi yapilir.
Algoritmada recursive metodlar kullanilmistir. Recursive metodlarla ilgili makaleyi inceleyebilirsiniz.
public void QuickSort(int[] dizi, int baslangic, int bitis)
{
int i;
if (baslangic < bitis)
{
i = partition(dizi, baslangic, bitis);
QuickSort(dizi, baslangic, i - 1);
QuickSort(dizi, i + 1, bitis);
}
}
public int partition(int[] A, int baslangic, int bitis)
{
int gecici;
int x = A[bitis];
int i = baslangic - 1;
for (int j = baslangic; j <= bitis - 1; j++)
{
if (A[j] <= x)
{
i++;
gecici = A[i];
A[i] = A[j];
A[j] = gecici;
}
}
gecici = A[i + 1];
A[i + 1] = A[bitis];
A[bitis] = gecici;
return i + 1;
}
Veysel Ugur KIZMAZ