Quick Sorting(퀵 정렬)

안녕하세요. 이번에 연구해 볼 과제는 Quick Sort(퀵 정렬)입니다. 이 정렬은 현재 존재하는 정렬 알고리즘 중에서 평균적인 상황일 때 최고의 성능을 보입니다. 평균적으로 시간복잡도 O(n log n)이 걸리고 최악의 경우 시간복잡도 O(n^2)이 됩니다. 퀵 정렬은 배열에서 피벗(기준)을 잡은 후에 피번 기준으로 작은 값은 왼쪽(오름차순이라면 오른쪽)으로, 큰 값은 오른쪽으로 이동시킵니다. 같은 알고리즘으로 피벗기준으로 왼쪽배열과 오른쪽 배열을 정렬합니다(재귀적으로).

그림 출처 : (https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

제가 퀵 정렬을 구현하면서 알게된 것들을 포스팅 하려고합니다..

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_ARR 1024
 
typedef int ELEMENT;
 
void swap(ELEMENT* a, ELEMENT* b) {
    ELEMENT temp = *a;
    *a = *b;
    *b = temp;
}
 
void quickSort(ELEMENT arr[], int from, int to) {
    ELEMENT pivot = from;
    ELEMENT left = pivot + 1, right = to - 1;
 
    if (from < to) {
        while (left <= right) {
            while (arr[pivot] >= arr[left] && left < to) left++;
            while (arr[pivot] <= arr[right] && right > from) right--;
            if (left < right) {
                swap(&arr[left], &arr[right]);
            }
        }
        swap(&arr[pivot], &arr[right]);
        pivot = right;
        quickSort(arr, from, pivot);
        quickSort(arr, pivot + 1, to);
    }
}
 
int main(void) {
    srand((unsinged int)time(NULL));
 
    ELEMENT arr[MAX_ARR];
 
    for (int i = 0; i < sizeof(arr) / sizeof(ELEMENT); i++) {
        arr[i] = rand();
    }
 
    quickSort(arr, 0, sizeof(arr) / sizeof(ELEMENT));
 
    for (int i = 0; i < sizeof(arr) / sizeof(ELEMENT); i++) {
        printf("arr[%d]:%d\n", i, arr[i]);
    }
    
 
    return 0;
}

피벗을 잡을때 저는 그냥 배열의 맨 처음에 있는 원소를 대입했는데, 피벗이 계속 최솟값이나 최대값으로 잡힐경우 시간복잡도 O(n^2)경우가 되기 때문에 피벗을 잡을 때도 다양한 방법으로 잡더라구요.. 랜덤으로 잡는다거나 배열에서 원소 몇개를 추출해서 그중의 가운데 값을 고른다거나.. 하지만 저는 그냥 예제로 배열의 첫번째 원소를 피벗으로 했습니다.

1.처음 고생한 것 18번째 라인 left<right 로 했을때.(현재는 from<to로 수정)

18번째 라인에서 조건식에 =를 뺏을 경우에 일어나는일은 배열 { 5,3,10,8,4,9,1,6,2,7 } 을 정렬하는 과정에서 발생합니다. 정렬을 시작하고 quickSort(arr,from=1,to=3)이 불렸을 때 상황을 표현하면 이런 상황입니다.

여기서는 from이 인덱스 1로 불리고 to가 3으로 적용되서 불렸는데요. 그다음 left와 right는 같은 2를 가리키고 있습니다. 여기서 18번 라인의 if문의 조건식을 적용시키면 left<right 가 false가 되죠. 그래서 정렬을 하지 않고 정렬을 끝내게 됩니다. 그러므로 19번째 라인에 left<right 대신에 from < to로 해주어야 제대로 돌아가게됩니다.

2.라인번호 19번의 논리 기호.

먼저 19번째 줄 left<right을 보면 1번에서 18째 줄을 from<to로 고쳐도 19번째 줄 while의 조건이 left<right이므로 위의 조건과 같습니다.

보시면, 18째 줄을 수정해서 while문으로 들어와도 조건이 left<right이므로 조건에 맞지않아 스왑하지 않고 빠져나오는 문제점이 있었어요. 그래서 19번째줄을 left<=right로 수정해서 제대로 돌아가게 만들었습니다.

3.라인번호 20,21번의 논리 기호.

이렇게 까지 수정해도 아직도 제코드에 문제점들이 많이 있었어요.. ㅠㅠ 최종적으로는 배열에 중복되는 숫자가 있을 경우 정렬하지 못하고 무한루프에 빠지게 되는거.. 확인하기 위해서 배열에 { 5,5,5,5,5 }를 넣고 정렬을 돌려봤습니다. 그랬더니 19번째 라인까지는 잘 들어오지만 큰 while문을 빠져나오지 못하는 상황이 발생합니다. 그 이유인 즉슨 이런 상황에서 20번,21번 라인의 조건문을 보시면

arr[pivot] (5) 와 arr[left]를 비교해서 left가 작으면 left의 위치를 이동시키는 겁니다. 하지만 여기서는 arr[pivot]>arr[left]는 false이므로 left는 움직이지 않죠. 마찬가지로 arr[pivot]<arr[right]또한 false이므로 right의 위치는 이동되지 않습니다. 반복문을 다돈후 22번줄에서 left<right가 ture이므로 left와 right를 스왑합니다. 그 후 19번으로 돌아가서 left<=right(true)이므로 다시 수행합니다. 그 후 반복...

따라서!! 20번,21번의 while문 조건에 등호를 넣어줘야 left와 right가 교차되면서 while문이 끝나고 다음으로 넘어갑니다.

이번 포스팅이 다른분들께 도움이 되시길 빌며.. face북 매일프로그래밍 페이지에 올라온 퀵정렬 코드 올리며 끝냅니다.

https://www.facebook.com/mailprogramming/posts/344787942672324

// Quicksort by 매일프로그래밍
 
void quicksort(int data[], int start, int end) {
    if (start < end) {
        int pivot = start;
        for (int i = start; i < end; i++) {
            if (data[i] < data[end]) {
                swap(data, i, pivot);
                pivot++;
            }
        }
        swap(data, pivot, end);
        quicksort(data, start, pivot - 1);
        quicksort(data, pivot + 1, end);
    }
}
 
void swap(int data[], int a, int b) {
    int temp = data[a];
    data[a] = data[b];
    data[b] = temp;
}
 
quicksort(arr, 0, arr.length - 1);