본문으로 바로가기

[Algorithm]퀵정렬 알고리즘(C++)

category Algorithm/정렬알고리즘 2018. 6. 4. 14:29

시간복잡도가 nlogn 인 정렬 알고리즘은 대표적으로 힙정렬, 병합정렬, 퀵정렬이 있다.

힙정렬은 지난번에 알아보았고 이번엔 nlogn 알고리즘중에서도 평균적으로 가장 성능을 잘 내는 퀵정렬에 대해 알아보겠따.

[Algorithm]힙정렬 알고리즘(C++)
힙정렬은 시간복잡도가 nlogn 으로 퀵정렬과 병합(합병)정렬과 같은 시간복잡도를 가진 정렬 알고리즘이다. 하지만 병합정렬과는 다르게 추가적인 메모리가 필요하지않고, 항상 nlogn의 정렬 성능을 보여주기때문..
dpdpwl.tistory.com

 

 

퀵정렬

최악의 경우 n^2의 성능을 내지만 사실 최악의경우는 잘 나오지 않는다.. 이경우를 제외하곤 평균적으로 nlogn 의 성능.

대부분의 상황에서 nlogn중 가장빠르다.

사실 퀵정렬은 딱히 복잡한게 없다. 정렬을할 배열에서 기준이 되는 수를 기준으로 왼편엔 기준보다 작은수, 오른편엔 기준보다 큰수 를 배치하는 작업을 반복하면 된다.

처음에 7size의 배열이 있다고 예를든다.


여기서 기준이되는 수(PIVOT)을 하나 잡아야한다 . 배열의 중앙을 PIVOT으로 잡겠다. ( 맨앞을 잡고 하는 방법도 있음)

중앙을 PIVOT으로 잡았으면 왼쪽끝과 오른쪽끝을 LEFT와 RIGHT 로 잡는다.


LEFTRIGHTPIVOT과 비교하여 LEFTPIVOT보다 큰수를 만나면

RIGHTPIVOT보다 작은수를 만나면 멈춰 서로 교환하게 되어있다.

이렇게 조건이 맞으면 멈춘 뒤 서로 교환을 한다.



LEFT가 RIGHT보다 커질때까지 반복을한다. (단, PIVOT을 만나면 더이상 가지않음)

LEFT는 6에서 멈추고 RIGHT는 3(PIVOT)에서 멈추었다. 이상태로 교환.



교환을 하게되면 LEFT와 RIGHT는 한칸씩 움직인다. 

이때, LEFT가 RIGHT보다 커졌기때문에 비교를 멈추고 왼쪽부분, 오른쪽부분을 다시 퀵정렬 하게된다.


왼쪽부분을 퀵정렬, 오른쪽부분을 퀵정렬 을 하다보면 보든 배열이 정렬이 되어진다



퀵정렬을 구현하는 C++소스를 보자


배열을 입력받은 뒤, 바로 quickSort 를 한다.

    int pivot = quick[(i+j)/2];
    int left = i;
    int right = j;

피벗과 left, right 커서의 위치를 정한다.

그리고 while 문을 돌면서 정렬을 시작한다. left가 right보다 커질때까지 반복하며 pivot을 만나면 멈춤.

    while(left<=right)
    {
        while(quick[left]<pivot) left++;
        while(quick[right]>pivot) right--;
        if(left<=right)
        {
            swap(quick[left],quick[right]);
            left++; right--;
        }
    }

좌,우 quick정렬 재귀함수로 돌린다.

    quickSort(i,right);
    quickSort(left,j);

이상으로 quick정렬에 대해 알아보았다, 자신이 만든 nlogn 알고리즘을 검증하고 싶다면 백준 2751번 에 한번 제출해보자.

2751번: 수 정렬하기 2
 
www.acmicpc.net