[정렬 알고리즘 - 3]퀵 정렬(Quick Sort)

Quick Sort

---

다음은 정렬 알고리즘 이름부터 빠른 Quick Sort입니다. Quick Sort는 빠른 알고리즘으로 O(NlogN)의 시간복잡도를 가지는 알고리즘인데요 한번 알아봅시다.

먼저 Quick Sort의 구동 방식을 말로 설명하자면 이러합니다.

---

1. pivot(기준점)을 기준으로 양 끝점(0,n이겠죠 보통)에서 비교를 시작한다(오름차순인 경우 오른쪽이 pivot보다 커야하고, 왼쪽이 작아야 합니다.)
2. 비교하면서 pivot과 값을 비교하고 값을 정렬하면서 중간쪽으로 온다.
3. 왼쪽(0)에서 시작한 기준점이 오른쪽(n)에서 시작한 기준점보다 커지게 되면 왼쪽에서 시작한 기준점을 기준으로 pivot을 정하고 다시 정렬한다.

---

무슨말인지 잘 모를 수가 있습니다. 동영상으로 보면 완전 이해가 잘 되는데 제가 봤던 링크는 바로 여기입니다. 여기

Quick Sort의 특징은 이거에요.

pivot을 기준으로 양 끝에서 비교해가면서 값을 정렬하다가 중간지점에서 교차하게 되면 pivot을 옮기게 되겠죠.

그렇게 되면 오름차순 기준으로 pivot 왼편엔 pivot보다 작은 값들, 오른쪽엔 pivot보다 큰 값들만 놓이게 되는 것!

이렇게 되면 pivot기준 왼쪽, 오른쪽을 퀵정렬 시켜버리면 되겠네요!!!

void qsort(int* data, int left, int right)
{
    int l = left;
    int r = right;
    int pivot = data[left];
    while(l<r)
    {
        while((data[r] >= pivot) && (l<r)) r--;
        data[l] = data[r];
        while((data[l] < pivot) && (l<r)) l++;
        data[r] = data[l];
    }
    data[l] = pivot;
    if(left<l)
        qsort(data,left,l-1);
    if(l<right)
        qsort(data,r+1,right);
}

코드를 보면 이해가 되시나요!? 중간에 값이 교차하면 다시 왼쪽 오른쪽을 퀵정렬! 퀵정렬을 설명하는게 생각보다 어렵네요...ㅋㅋㅋㅋㅋㅋㅋㅋ 무튼 이렇게 마무리하고, 생각보다 간단하죠..? 이젠 sort를 사용한 예제를 접해보겠습니다~!!!