Sıralama algoritmaları, verilerimizin sıralı bir şekilde olmasını sağlayabilmek için kullandığımız yöntemlerdir.

Peki verilerimizin sıralı olmasının önemi nedir?
Arama yaparken Binary Search algoritması ile sıralı verilerde çok hızlı arama gerçekleştirebiliriz. Daha farklı bir örnek vermek gerekirse en en kısa yol hesabı için de verilerin sıralı bir şekilde bulunması gerekmektedir. Bu ve bunun gibi birçok sebebe dayanarak verilerimizin sıralı bir şekilde tutumasının faydalı olacağını söyleyebiliriz.

Bu makalede sıralama algoritmalarından Quick Sort algoritmasını inceleyeceğiz.

Kısaca, bu algoritma diziler ile işlem yapmaktadır. Dizinin ortasındaki sayıyı bulur ve bu sayıyı baz alarak diğer sayıları bu sayıdan küçük ya da büyük diyerek böler. Sonuçta ortaya çıkan gruplar için aynı işlem tekrarlanır. Bu yönteme divide and conquer yaklaşımı da denmektedir.

Sayısal bir örnek verelim:

sayilar = {9, 4, 6, 7, 3, 8, 1}

1. Dizinin ortasındaki sayı bulunur. sayilar[3] = 7
2. Seçilen elemanı dizideki elemanlarla karşılaştırarak büyük ve küçükleri gruplandır    3 1 4 6 (7) 9 8
3. Küçük elemanların ortasınıdaki sayı bulunur. sayilar[2] = 1
4. Seçilen elemanı dizideki elemanlarla karşılaştırarak büyük ve küçükleri gruplandır  (1) 3 4 6
5. Büyük elemanların ortasındaki sayı bulunur. sayilar[1] = 9
6. Seçilen elemanı dizideki elemanlarla karşılaştırarak büyük ve küçükleri gruplandır 8 (9)
7. 4.maddedeki büyük elemanların ortasındaki sayı bulunur. sayilar[1] = 4
8. Seçilen elemanı dizideki elemanlarla karşılaştırarak büyük ve küçükleri gruplandır 3 (4) 6
9. Birleştirme işlemine geçilir. Önce son grup birleştirilir:
3 4 6
1 3 4 6
1 3 4 6 7
1 3 4 6 7 8 9
şeklinde sıralama işlemi yapılır.

Algoritmada recursive metodlar kullanılmıştır. 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;
        }