퀵정렬(Quick Sort) 구현

퀵정렬(Quick Sort) 구현

이번에는 퀵정렬 알고리즘을 구현을 해보겠다.

퀵정렬이 이미 구현되어 있는 함수도 있기야 하지만 퀵정렬이 어떻게 돌아가는지 알기 위해서 구현을 한번 해보았다.

퀵정렬 구현되어 있는 함수 -> qsort() 함수

#include <iostream>
using namespace std;
void quick_sort(int data[], int left, int right)
{
    int i, j, key, temp;
    if (left < right) {
        i = left, j = right;
        key = data[left];
        do {
            do {
                i++;
            } while (data[i] < key);
            do {
                j--;
            } while (data[j] > key);
            if (i < j) {
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        } while (i < j);
        temp = data[left];
        data[left] = data[j];
        data[j] = temp;
        quick_sort(data, left, j);
        quick_sort(data, j + 1, right);
    }
}
int main()
{
    int arr[] = { 4,100,8,52,64,92,10,2,-1,0 };
    int size = sizeof(arr) / sizeof(int);
    quick_sort(arr, 0, size);
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
}

퀵정렬 알고리즘은 이러하다.

이 알고리즘이 이해가 가지 않는다면 일단 그림으로 보고 오기를 바란다. -> 퀵정렬 알고리즘 그림으로 설명

그림을 보고 왔으면 코드가 이해가 될것이다. 

8행에서 기준키로 첫번째 배열을 넣어준다.

10~12행에서 1번째 인덱스부터 기준키보다 큰 값을 찾는다.

13~15행에서 마지막 인덱스부터 기준키보다 작은 값을 찾는다.

16~20행은 큰값과 작은 값을 서로 바꿔준다.

22~24행은 만약 큰 값과 작은 값 위치가 서로 교차하게 되면 값을 바꾸지 않고 기준키와 작은 값을 서로 바꿔주게 된다.

그리고 정렬된 데이터들을 보면 왼쪽에는 작은 값이, 오른쪽에는 큰 값이 위치하게 되는것을 볼수가 있다.

25행에서 기준키를 중심으로 양분을 한다.

이런식으로 진행이 된다고 보면 된다.