퀵 정렬(quick sort)

• 가장 빠른 정렬 알고리즘 중 하나
• 피벗을 기준으로 피벗보다 작은 요소로 이루어진 부분과 피벗보다 큰 요소 이루어진 부분으로 나눔을 반복함으로써 최종적으로 정렬 된다.
• 즉 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹의 개수가 1이 되면 정렬을 마친다.
• 서로 이웃하지 않고 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않은 알고리즘이다.
• 시간 복잡도는 O(n log n)
• 정렬할 배열의 초깃값이나 피벗의 선택 방법에 따라 시간 복잡도가 증가하는 경우도 있다.
• 최악의 시간 복잡도는 O(n^2)이 된다.

배열을 두 그룹으로 나누기

1. 피벗 이하의 요소를 배열 왼쪽으로 옮긴다.
   • a[pl] >= x 가 성립할 때까지 pl을 오른쪽으로 스캔
2. 피벗 이상의 요소를 배열 오른쪽으로 옮긴다.
   • a[pr] <= x 가 성립할 때까지 pr을 왼쪽으로 스캔
3. pl과 pr이 교차하면 그룹을 나누는 과정이 끝나고 배열은 두 그룹으로 나누어진다.
   • 피벗 이하의 그룹 : a[0] ~ a[pl - 1]
   • 피벗 이상의 그룹 : a[pr + 1] ~ a[n - 1]
   • pl > pr + 1 인 경우에는 피벗과 일치하는 값을 가진 그룹이 생길 수 있다 : a[pr + 1] ~ a[pl - 1]

퀵 정렬은 분할 정복 알고리즘이므로 재귀 호출을 사용하여 구현할 수 있다.

• 요소의 개수가 2개 이상인 각 그룹을 나누는 작업을 반복하기 위해 재귀 호출

//퀵 정렬
static void quickSort(int[] a, int left, int right) {
    int pl = left;               //왼쪽 커서
    int pr = right;              //오른쪽 커서
    int x = a[(pl + pr) / 2];    //피벗
    
    //배열 a를 피벗 x를 기준으로 나눈다
    do {
        while (a[pl] < x) pl++;
        while (a[pr] > x) pr--;
        
        if (pl <= pr)
            swap(a, pl++, pr--);
    } while (pl <= pr);
    
    //요소의 개수가 2개 이상인 그룹만 나누기 위한 조건
    if (left < pr) quickSort(a, left, pr);      //피벗 이하인 부분
    if (pl < right) quickSort(a, pl, right);    //피벗 이상인 부분
}

 

비재귀적인 퀵 정렬

• 사용하여 비재귀적인 퀵 정렬을 구현할 수 있다.
• 스택에 푸시한 값은 나눌 배열의 첫 요소와 끝 요소의 인덱스이다.
• 배열을 나누는 작업이 끝나면 하위 그룹 인덱스와 상위 그룹 인덱스를 푸시한다.
• 스택에서 팝한 범위를 나누는 작업을 반복하여 정렬을 수행한다.
• 스택이 비면 정렬이 끝난다.

// 퀵정렬(비재귀버전)
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 (a[pr] > x) 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);     //인덱스를 푸시
        }
    }
}

 

분할한 그룹 중 요소의 개수가 적은 그룹을 먼저 나누기

• 배열을 나눈 뒤에 얻는 하위 그룹과 상위 그룹의 요소 개수를 비교하여 많고 적음에 따라 푸시 순서를 바꾸면 스택에 최대로 쌓이는 데이터 수를 조절할 수 있다.
• 요소의 개수가 많은 그룹을 먼저 푸시하면 요소의 개수가 적은 그룹을 먼저 나누게 된다.
• 즉 요소의 개수가 적은 배열일수록 적은 횟수로 분할을 종료할 수 있게 되고 스택에 쌓이는 데이터의 최대 개수가 적어진다.
• 만약 배열의 길이가 n이라고 한다면 스택에 쌓이는 데이터의 최대 개수는 log n보다 적게 된다.

피벗 선택하기

• 피벗을 선택하는 방법에 따라 퀵 정렬의 실행 효율에 큰 영향을 미친다.
• [방법 1] : 나눌 배열의 요소 개수가 3 이상이면 임의로 요소 3개를 선택하고 그 중에서 중간 값인 요소를 피벗으로 선택한다.
• [방법 2] : 나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음 가운데 요소와 끝에서 두 번째 요소를 교환한다. 피벗으로 끝에서 두 번째 요소의 값(a[right - 1])을 선택하여 나눌 대상의 범위를 a[left + 1] ~ a[right - 2]로 좁힌다.