퀵 정렬(Quick Sort)

퀵 정렬

정렬할 전체 원소에 대해서 정렬을 수행하지 않는다.

먼저 기준 값을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다.

왼쪽 부분집합에는 기준 값보다 작은 원소들을 이동시키고

오른쪽 부분집합에는 기준 값보다 큰 원소들을 이동시킨다.

1단계

가장 왼쪽의 원소를 기준 값(Pivot)으로 정한후

왼쪽에서는 기준 값(27)보다 큰 원소(37)를, 오른쪽에서는 기준 값보다 작은 원소(18)를 찾는다.

두 원소의 자리를 바꾼다.

계속 진행하여 기준 값(27)보다 큰 원소(62)와 작은 원소(16)을 찾는다.

마찬가지로 두 원소의 자리를 바꾼다.

또 다시 반복하여 기준 값(27)보다 큰 원소(59)와 작은 원소(12)를 찾는다.

하지만 R <= L 이기 때문에 비교를 멈추고 R의 원소(12)와 기준 값(27)을 바꾼다.

2단계

바꾼 기준 값(27)은 자신의 자리를 찾았기 때문에 왼쪽 부분집합과 오른쪽 부분집합에 대해 1단계 작업을 반복한다.

기준 값(12)보다 큰 원소(18)와 작은 원소(2)를 찾은 후 자리를 바꾼다.

자리를 바꾼 후 L++, R-- 결과, R <= L 이 되었기 때문에 R의 원소(2)와 기준 값(12)을 바꾼다.

3단계

기준 값(12)은 자신의 자리를 찾았기 때문에 왼쪽 집합과 오른쪽 집합에 대해 정렬을 시작한다.

왼쪽 집합의 경우 이미 정렬이 되어있고 오른쪽 집합의 경우 R <= L 이므로 두 원소(18, 16)의 자리를 바꾼다.

4단계

처음 기준 값(27)의 왼쪽 집합은 모두 정렬이 완료되었으므로 오른쪽 집합에 대해 정렬을 시작한다.

기준 값(59)보다 큰 원소(62)와 작은 원소(37)를 찾고 자리를 바꾼다.

계속 진행하여 기준 값(59)보다 큰 원소(62)와 작은 원소(49)를 찾는다.

하지만 R <= L 이므로 R의 원소(49)와 기준 값(59)의 자리를 바꾼다.

5단계

기준 값(59)은 자신의 자리를 찾았기 때문에 왼쪽 집합과 오른쪽 집합에 대해 정렬을 시작한다.

오른쪽 집합의 경우 원소가 하나이기 때문에 자동으로 정렬이 되었고

왼쪽 집합의 경우 R <= L 이므로 두 원소(49, 37)의 자리를 바꾼다.

최종적으로 정렬이 되었음을 알 수 있다.

시간복잡도

Best, Average

Worst

실행코드 / 결과