Quick Sort

Kategori: C , 02 Temmuz 2019 , JanFranco


Quick sort algoritması, dizide bir pivot eleman seçer. Bu eleman genellikle en sonki eleman seçililir. İki adet değişken tanımlanır i ve j. j değişkeni ile tüm dizi taranır ve eğer bir eleman pivot elemandan küçük ise i değişkeninin değeri bir artırılır ve dizinin i. indexindeki eleman ile j. indexindeki eleman yer değiştirilir. İkinci bir değişkenin olmasının ve sadece belirli durumlarda artmasının sebebi, pivottan küçük elemanları bir tarafa, büyük elemanları bir tarafa toplamaktır. Son olarak i değişkenin bir fazlası olan indexteki eleman ile pivot eleman yer değiştirilir. Bu şekilde aşağıdaki gibi bir görünüm elde edilir:

pivottan küçük elemanlar - pivot - pivottan büyük elemanlar

Küçük elemanlar ve büyük elemanlar kendi içlerinde düzensiz olabilir. Bu sebeple başlangıç ve bitiş indexleri verilerek bu iki kısım bir diziymiş gibi davranılır ve tekrar aynı işlemlerden geçirilir. Bu sürekli tekrar eder. Başlangıç ve bitiş indexlerini verdiğimiz için, bu işlemlerin ne zaman duracağını bitiş > başlangıç koşulu ile belirleyebiliriz. Rastgele 10 elemandan oluşan bir array'i quick sort ile sıralayalım:


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 100

int partition_(int arr[], int low, int high){
    int pivot = arr[high], j, i = low - 1, temp;
    for(j=low; j<=high-1; j++){
        if(arr[j] <= pivot){
            i++;
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
    temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    return i+1;
}

void quick_sort(int arr[], int low, int high){
    if(low < high){
        int pi = partition_(arr, low, high);
        quick_sort(arr, low, pi-1);
        quick_sort(arr, pi+1, high);
    }
}

void print_array(int arr[]){
    int i;
    for(i=0; i<N; i++){
        printf("%d  ", arr[i]);
    }
}

int main() {

    int arr[N], i;
    srand(time(NULL));

    for(i=0; i<N; i++){
        arr[i] = rand() % N;
    }
    print_array(arr);
    printf("\nAfter sorting:\n");
    quick_sort(arr, 0, N-1);
    print_array(arr);

    return 0;
}
Her iteration'da ne olduğunu daha iyi görmek için:

int partition_(int arr[], int low, int high){
    int pivot = arr[high], j, i = low - 1, temp;
    for(j=low; j<=high-1; j++){
        if(arr[j] <= pivot){
            i++;
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
        printf("\n%d. iteartion (partition_)\n", j);
        print_array(arr);
    }
    temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;

    return i+1;
}
Bu fonksiyonu kullanarak programı çalıştırdığımızdaki sonuçlar:

7  17  10  15  5  1  10  19  11  3  5  13  13  2  8  16  1  2  5  18
0. iteartion (partition_)
7  17  10  15  5  1  10  19  11  3  5  13  13  2  8  16  1  2  5  18
1. iteartion (partition_)
7  17  10  15  5  1  10  19  11  3  5  13  13  2  8  16  1  2  5  18
2. iteartion (partition_)
7  17  10  15  5  1  10  19  11  3  5  13  13  2  8  16  1  2  5  18
3. iteartion (partition_)
7  17  10  15  5  1  10  19  11  3  5  13  13  2  8  16  1  2  5  18
4. iteartion (partition_)
7  17  10  15  5  1  10  19  11  3  5  13  13  2  8  16  1  2  5  18
5. iteartion (partition_)
7  17  10  15  5  1  10  19  11  3  5  13  13  2  8  16  1  2  5  18
6. iteartion (partition_)
7  17  10  15  5  1  10  19  11  3  5  13  13  2  8  16  1  2  5  18
7. iteartion (partition_)
7  17  10  15  5  1  10  19  11  3  5  13  13  2  8  16  1  2  5  18
8. iteartion (partition_)
7  17  10  15  5  1  10  11  19  3  5  13  13  2  8  16  1  2  5  18
9. iteartion (partition_)
7  17  10  15  5  1  10  11  3  19  5  13  13  2  8  16  1  2  5  18
10. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  19  13  13  2  8  16  1  2  5  18
11. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  13  19  13  2  8  16  1  2  5  18
12. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  13  13  19  2  8  16  1  2  5  18
13. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  13  13  2  19  8  16  1  2  5  18
14. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  13  13  2  8  19  16  1  2  5  18
15. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  13  13  2  8  16  19  1  2  5  18
16. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  13  13  2  8  16  1  19  2  5  18
17. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  13  13  2  8  16  1  2  19  5  18
18. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  13  13  2  8  16  1  2  5  19  18
0. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  13  13  2  8  16  1  2  5  18  19
1. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  13  13  2  8  16  1  2  5  18  19
2. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  13  13  2  8  16  1  2  5  18  19
3. iteartion (partition_)
7  17  10  15  5  1  10  11  3  5  13  13  2  8  16  1  2  5  18  19
4. iteartion (partition_)
5  17  10  15  7  1  10  11  3  5  13  13  2  8  16  1  2  5  18  19
5. iteartion (partition_)
5  1  10  15  7  17  10  11  3  5  13  13  2  8  16  1  2  5  18  19
6. iteartion (partition_)
5  1  10  15  7  17  10  11  3  5  13  13  2  8  16  1  2  5  18  19
7. iteartion (partition_)
5  1  10  15  7  17  10  11  3  5  13  13  2  8  16  1  2  5  18  19
8. iteartion (partition_)
5  1  3  15  7  17  10  11  10  5  13  13  2  8  16  1  2  5  18  19
9. iteartion (partition_)
5  1  3  5  7  17  10  11  10  15  13  13  2  8  16  1  2  5  18  19
10. iteartion (partition_)
5  1  3  5  7  17  10  11  10  15  13  13  2  8  16  1  2  5  18  19
11. iteartion (partition_)
5  1  3  5  7  17  10  11  10  15  13  13  2  8  16  1  2  5  18  19
12. iteartion (partition_)
5  1  3  5  2  17  10  11  10  15  13  13  7  8  16  1  2  5  18  19
13. iteartion (partition_)
5  1  3  5  2  17  10  11  10  15  13  13  7  8  16  1  2  5  18  19
14. iteartion (partition_)
5  1  3  5  2  17  10  11  10  15  13  13  7  8  16  1  2  5  18  19
15. iteartion (partition_)
5  1  3  5  2  1  10  11  10  15  13  13  7  8  16  17  2  5  18  19
16. iteartion (partition_)
5  1  3  5  2  1  2  11  10  15  13  13  7  8  16  17  10  5  18  19
0. iteartion (partition_)
5  1  3  5  2  1  2  5  10  15  13  13  7  8  16  17  10  11  18  19
1. iteartion (partition_)
1  5  3  5  2  1  2  5  10  15  13  13  7  8  16  17  10  11  18  19
2. iteartion (partition_)
1  5  3  5  2  1  2  5  10  15  13  13  7  8  16  17  10  11  18  19
3. iteartion (partition_)
1  5  3  5  2  1  2  5  10  15  13  13  7  8  16  17  10  11  18  19
4. iteartion (partition_)
1  2  3  5  5  1  2  5  10  15  13  13  7  8  16  17  10  11  18  19
5. iteartion (partition_)
1  2  1  5  5  3  2  5  10  15  13  13  7  8  16  17  10  11  18  19
0. iteartion (partition_)
1  2  1  2  5  3  5  5  10  15  13  13  7  8  16  17  10  11  18  19
1. iteartion (partition_)
1  2  1  2  5  3  5  5  10  15  13  13  7  8  16  17  10  11  18  19
4. iteartion (partition_)
1  1  2  2  5  3  5  5  10  15  13  13  7  8  16  17  10  11  18  19
5. iteartion (partition_)
1  1  2  2  5  3  5  5  10  15  13  13  7  8  16  17  10  11  18  19
4. iteartion (partition_)
1  1  2  2  5  3  5  5  10  15  13  13  7  8  16  17  10  11  18  19
8. iteartion (partition_)
1  1  2  2  3  5  5  5  10  15  13  13  7  8  16  17  10  11  18  19
9. iteartion (partition_)
1  1  2  2  3  5  5  5  10  15  13  13  7  8  16  17  10  11  18  19
10. iteartion (partition_)
1  1  2  2  3  5  5  5  10  15  13  13  7  8  16  17  10  11  18  19
11. iteartion (partition_)
1  1  2  2  3  5  5  5  10  15  13  13  7  8  16  17  10  11  18  19
12. iteartion (partition_)
1  1  2  2  3  5  5  5  10  7  13  13  15  8  16  17  10  11  18  19
13. iteartion (partition_)
1  1  2  2  3  5  5  5  10  7  8  13  15  13  16  17  10  11  18  19
14. iteartion (partition_)
1  1  2  2  3  5  5  5  10  7  8  13  15  13  16  17  10  11  18  19
15. iteartion (partition_)
1  1  2  2  3  5  5  5  10  7  8  13  15  13  16  17  10  11  18  19
16. iteartion (partition_)
1  1  2  2  3  5  5  5  10  7  8  10  15  13  16  17  13  11  18  19
8. iteartion (partition_)
1  1  2  2  3  5  5  5  10  7  8  10  11  13  16  17  13  15  18  19
9. iteartion (partition_)
1  1  2  2  3  5  5  5  10  7  8  10  11  13  16  17  13  15  18  19
10. iteartion (partition_)
1  1  2  2  3  5  5  5  10  7  8  10  11  13  16  17  13  15  18  19
8. iteartion (partition_)
1  1  2  2  3  5  5  5  10  7  8  10  11  13  16  17  13  15  18  19
9. iteartion (partition_)
1  1  2  2  3  5  5  5  7  10  8  10  11  13  16  17  13  15  18  19
13. iteartion (partition_)
1  1  2  2  3  5  5  5  7  8  10  10  11  13  16  17  13  15  18  19
14. iteartion (partition_)
1  1  2  2  3  5  5  5  7  8  10  10  11  13  16  17  13  15  18  19
15. iteartion (partition_)
1  1  2  2  3  5  5  5  7  8  10  10  11  13  16  17  13  15  18  19
16. iteartion (partition_)
1  1  2  2  3  5  5  5  7  8  10  10  11  13  13  17  16  15  18  19
13. iteartion (partition_)
1  1  2  2  3  5  5  5  7  8  10  10  11  13  13  15  16  17  18  19
16. iteartion (partition_)
1  1  2  2  3  5  5  5  7  8  10  10  11  13  13  15  16  17  18  19

After sorting:
1  1  2  2  3  5  5  5  7  8  10  10  11  13  13  15  16  17  18  19


Sonraki Yazı: Merge Sort
Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın