[Algorithm] 퀵 정렬 (Quick Sort)1_JAVA

일반적으로 가장 많이 사용 되는 퀵정렬(Quick Sort)에 대해 공부해 보자.

 

퀵정렬은 이름처럼 졍렬 속도가 매우 빠른 것에서 착안하여 알고리즘 개발자 찰스 앤터니 리터드 호어(C. A. R. Hoare)가 착안해 직접이름을 붙였다.

 

[개요]

[배열을 두그룹으로 나누기]

그룹을 나누기 위해서는 피벗 이하의 요소를 배열 왼쪽으로, 피벗 이하의 요소들을 오른 쪽으로 옮겨야 한다.

 - a[pl] >= x 가 성렵하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔함
 - a[pl] <= x 가 성렵하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔함

이과정을 거쳐 pl과 pr이 멈추게 되면

pl이 위치한 지점은 피벗값이 이상의 요소가 있는 지점이고 pr이 위치한 지점은 피벗 이하의 요소가 있는 지점이다.

여기서 pl(왼쪽)과 pr(오른쪽) 커서가 가리키는 요소의 값을 교환하면 

피벗이하의 값은 왼쪽으로 이동하고 피벗 이상의 값은 오른쪽을 이동하게 된다.

이런 스캔을 계속하게 되면 나중에는 두 커서가 교차하게 되는데 그럼 이때는 그룹 나누는 과정이 끝이 나게 되고 두그룹으로 나누어 지게 된다.

- 피벗 이하의 그룹 : a[0], ··· , a[pl -1]
- 피벗 이상의 그룹 : a[pr +1], ··· , a[n -1]

이렇게 그룹을 나누는 작업이 끝난 다음 pl > pr +1 이면 다음과 같은 그룹이 생기게 된다.

- 피벗과 같은 값을 갖는 그룹 : a[pr +1], ··· , a[pl-1] 

만일 피벗과 같은 값을 갖는 그룹이 만들어 진다면,

이때도 전과 마찬가지로 동일한 요소를 교환하면 된다(어차피 시도는 많아도 1회 이므로)

이처럼 피벗을 선택하고 배열을 나누고 정렬하는 것은 성능에도 영향을 미칠 수 있는 문제이다.

 

[퀵정렬 구현]

배열을 피벗기준으로 나눈 것에서 좀 더 발전한 것이 바로 퀵정렬이다.

퀵정렬은 다시 말해 위와 같은 배열을 그룹 안에 구성요소의 개수가 하나일때 까지 반복해서 나누는 과정이다.

즉 구성요소가 1인 그룹은 더이상 나누지 않고 2개 이상이라면 계속해서 나누면 된다.

- pr이 맨 앞 보다 오른쪽에 있으면(left < pr) 왼쪽 그룹을 나눈다.
- pl이 맨 뒤 보다 왼쪽에 있으면(pl < right) 오른쪽 그룹을 나눈다.
- 가운데 그룹이 생기는 경우 더이상 나눌 필요가 없으므로 나눌 대상에서는 제외를 시켜야 한다.