[자바 Do It! 알고리즘]Chapter06 정렬 (퀵 정렬)

[퀵 정렬]

1. 퀵 정렬은 가장 빠른 정렬 알고리즘 중의 하나입니다.

2. 퀵정렬 순서

1) 배열을 두 그룹으로 나누기

(1) 피벗을 x, 왼쪽 끝 요소의 인덱스 pl을 왼쪽 커서, 오른쪽 끝 요소의 인덱스 pr을 오른쪽 커서라고 하겠습니다.

5(pl)

7

1

4

6(x,pivot)

2

3

9

8(pr)

(2) 그룹을 나누려면 피벗 이하의 요소를 배열 왼쪽으로, 이상의 요소를 배열 오른쪽으로 옮겨야 합니다.

☞ a[pl] >= x 가 성립하는 요소를 찾을 때 까지 pl을 오른쪽으로 스캔합니다.

☞ a[pr] <= x가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔합니다.

(3) (2) 과정을 진행하면 아래 그림의 위치에서 pl과 pr이 멈춥니다.

5

7(pl)

1

4

6(x,pivot)

2

3(pr)

9

8

(4) 현 pl과 pr의 위치를 교환하고, (2) 과정을 더 진행합니다. 그러면 결과는 이렇게 됩니다.

5	3	1	4	2(pr)	6(pl)	7	9	8
피벗 이하					피벗 이상

(5) 배열은 아래처럼 두 그룹으로 나누어집니다.

☞ 피벗 이하의 그룹 : a[0], ..., a[pl-1]

☞ 피벗 이상의 그룹 : a[pr + 1], ..., a[n-1]

(6) 또 그룹을 ㅏㄴ누는 작업이 끝난 다음 pl > pr + 1 인 경우에는 다음과 같은 그룹이 생길 수 있습니다.

☞ 피벗과 일치하는 값을 가지는 그룹 : a[pr + 1], ..., a[pl -1]

2) 1)의 과정을 그룹을 나누는 방식으로 세분화 시킵니다.

(1) 요소의 개수가 1갱니 그룹은 더 이상 그룹을 나눌 피룡가 없으므로 요소의 개수가 2개 이상인 그룹만 나누면

아래 처럼 배열을 반복해서 나누게 됩니다.

☞ pr이 a[0] 보다 오른쪽에 있으면 (left < pr> 왼쪽 그룹을 나눕니다.

☞ pl이 a[8] 보다 왼쪽에 있으면 (pl < right) 오른쪽 그룹을 나눕니다.

※ (left < pr), (pl < right) 는 모두 그룹의 개수가 1개인 경우에는 성립하지 않는 조건입니다.

다시 말해 요소의 개수가 2개 이상인 그룹만이 나누기 위해 필요한 조건입니다.

☞ quickSort 메서드는 배열 a, 나눌 구간의 첫 번째 요소(left), 마지막 요소(right)의 인덱스를 매개변수로 받습니다.