6-6. 퀵 정렬(Quick Sort)

퀵 정렬 살펴보기

• 가장 빠른 정렬 알고리즘 중 하나
• 피벗 설정과 그룹 나눔을 반복해 모든 그룹의 요소가 한 개가 되면 정렬을 마침
• 피벗은 마음대로 선택 가능, 양쪽 그룹 어느 곳에 포함시켜도 상관 없음

 

 

 

 

 

배열을 두 그룹으로 나누기

 

 

 

• 피벗: x
• 왼쪽 커서: pl
• 오른쪽 커서: pr

 

 

※ 피벗 이하의 요소를 배열 왼쪽으로, 이상의 요소를 배열 오른쪽으로 옮기기 위해 수행해야 할 작업

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

 

 

 

 

• pl이 위치한 지점: 피벗 값 이상의 요소가 있는 지점
• pr이 위치한 지점: 피벗 값 이하의 요소가 있는 지점

 

a[pl]과 a[pr]의 값을 교환해 피벗 이하의 값은 왼쪽으로 이동, 피벗 이상의 값은 오른쪽으로 이동

 

 

 

다시 스캔을 진행하면 왼쪽과 오른쪽 커서는 위 그림의 위치에서 멈추고, 다시 이 두 요소a[pl], a[pr]의 값을 교환

 

 

 

pl과 pr이 교차하면 그룹을 나누는 과정이 끝나고, 배열은 아래와 같이 두 그룹으로 나누어짐

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

 

 

 

그룹을 나누는 작업이 끝난 다음 pl > pr + 1인 경우에는 다음과 같은 그룹이 생길 수 있음

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

 

 

 

[실습 코드]

do {
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr) 
                swap(a, pl++, pr--);
        } while(pl <= pr);
 

 

 

 

 

 

퀵 정렬

배열 나누기를 발전시켜 요소의 개수가 2개 이상인 그룹을 반복해서 나눔

1. pr이 a[0]보다 오른쪽에 있으면(left < pr) 왼쪽 그룹을 나눔
2. pl이 a[n - 1]보다 왼쪽에 있으면(pl < right) 오린쪽 그룹을 나눔

※ left < pr, pl < right는 모두 그룹의 개수가 1개인 경우에는 성립하지 않는 조건, 즉 요소의 개수가 2개 이상인 그룹만이 나누기 위해 필요한 조건이다.

 

 

[실습 코드]

static void quickSort(int[] a, int left, int right) {
        int pl = left; //왼쪽 커서
        int pr = right; //오른쪽 커서
        int x = a[(pl + pr) / 2]; //피벗
        
        do {
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr)
                swap(a, pl++, pr--);
        } while(pl <= pr);
        
        if(left < pr) quickSort(a, left, pr);
        if(pl < right) quickSort(a, pl, right);
    }

 

 

 

 

 

비재귀적인 퀵 정렬

quickSort 메서드를 비재귀적으로 구현하기 위해서는 총 2개의 '스택'을 사용

1. lstack: 나눌 범위의 왼쪽 끝 요소의 인덱스를 저장
2. rstack: 나눌 범위의 오른쪽 끝 요소의 인덱스를 저장

 

 

 

[실습 코드]

static void quickSort(int[] a, int left, int right) {
        IntStack lstack = new IntStack(right - left + 1);
        IntStack rstack = new IntStack(right - left + 1);
        
        lstack.push(left);
        rstack.push(right);
        
        while(lstack.isEmpty() != true) {
            int pl = left = lstack.pop(); //왼쪽 커서
            int pr = right = rstack.pop(); //오른쪽 커서
            int x = a[(left + right) / 2]; //피벗
            
            do {
                while(a[pl] < x) pl++;
                while(x < a[pr]) pr--;
                if(pl <= pr)
                    swap(a, pl++, pr--);
            } while(pl <= pr);
            
            if(left < pr) {
                lstack.push(left);
                rstack.push(pr);
            }
            
            if(pl < right) {
                lstack.push(pl);
                rstack.push(right);
            }

 

 

 

 

 

피벗 선택하기

피벗을 선택하는 방법은 퀵 정렬의 실행 효율에 큰 영향

 

 

방법1. 나눌 배열의 요소 개수가 3 이상이면 임의로 요소 3을 선택하고 그중에서 중앙값인 요소를 피벗으로 선택

이 경우 최악으로 그룹이 나누어지는 경우(피벗의 값만 있는 그룹-나머지 그룹)는 피할 수 있음

 

 

 

방법2.	나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음 가운데 요소와 끝에서 두 번째 요소를 교환.
	피벗으로 끝에서 두 번째 요소의 값(a[right - 1])을 선택해 나눌 대상의 범위를 a[left + 1] ~ a[right - 2]
	로 좁힌다.

나눌 그룹의 크기가 한쪽으로 치우치는 것을 피하면서도 나눌 때 스캔할 요소를 3개씩 줄일 수 있다는 장점.

-> 조금 더 빠른 속도로 정렬 가능

 

 

예)

a. 정렬하기 전 상태. 첫 요소(8), 가운데 요소(4), 끝 요소(0)를 선택해 이 세 요소를 정렬
b. 첫 요소는 0, 가운데 요소는 4, 끝 요소는 8이 됨. 여기에서 가운데 요소(4)와 끝에서 두 번째 요소(1)를 교환
c. 끝에서 두 번째 요소(4)가 피벗. a[left]는 피벗 이하의 값이고 a[right - 1]과 a[right]는 피벗 이상의 값

 

a.

 

 

b.

 

 

c.