퀵 정렬

퀵 정렬

찰스 앤터니 리처드 호어(C. A. R. Hoare)가 알고리즘의 정렬 속도가 매우 빠른 데서 착안해 직접 붙인 이름이다.

범위에 있는 배열 요소들에 대해서 기준 값(=피벗) 하나를 정하고 기준 값과 정렬 조건(작은순, 큰 순 등)에 따라 좌우에 있는 요소들을 교환하며, 정렬을 마칠 때까지 지속적으로 좌우로 범위를 분할해가면서 정렬하는 알고리즘이다.

자세한 부분은 그림을 참고하면 이해를 돕는데 좋을 것이라 생각한다.

Do it 자료구조와 함께 배우는 알고리즘 입문

---

   static void swap(int[] a, int idx1 , int idx2){
        int t = a[idx1]; a[idx1] = a[idx2] ; a[idx2] = t;
    }

    static void quickSort(int[] a, int left, int right){
        int pl = left;  // 좌측 포인터
        int pr = right; // 우측 포인터
        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(pl < right) quickSort(a,pl,right); // 기준보다 큰 부분 정렬
        if(pr > left) quickSort(a,left,pr); // 기준보다 작은 부분 정렬

    }

    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);

        System.out.println("퀵 정렬");
        System.out.print("요솟수 : ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];

        for(int i = 0 ; i < nx ; i++){
            System.out.print("x[" + i + "] :");
            x[i] = stdIn.nextInt();
        }
        quickSort(x , 0, nx-1);

        System.out.println();
        System.out.println("오름차순으로 정렬했습니다");
        for(int i = 0 ; i < nx ; i++)
            System.out.println("x[" + i + "] = " + x[i]);
    }

  최초로 pl은 첫번째 요소 pr은 마지막 요소의 인덱스가 저장된 후 기준값을 중앙에 있는 요소로 잡고 시작한다. 

다음으로 기준 값과 비교해가며 양방향에 교환할 요소를 찾고 교환하며 진행해나간다. 그러다보면 기준 값과 동일한 위치까지 좌우 포인터가 위치하게 된다. 그리고 기준 값은 그대로 다시 저장되고 서로 교차해나간다.

 

  여기서 한 가지 생각해볼 것은 두 포인터가 기준 값 위치에 도착했을경우 교환을해도 값은 그대로이다. 그럼 불필요한 작업아닌가 ? 만약 불필요한 작업을 하지 않기 위해서 조건문으로 pl == pr을 별도로 작성하여 체크한다고 생각해보자 단지 기존에는 1번만 값을 그 자리에 넣으면 끝날 것을 반복문을 수행하는 동안 계속 조건문을 체크해야하는 비용이 발생한다.

 

다음으로 기준 값을 통하여 정렬된 요소들을 다시 좌우로 분할하여 기준을 세우고 정렬하는 일을 정렬이 완료될 때까지 수행하면 된다. 언제 정렬이 완료되는가는 위에 코드를 보면 쉽게 알 수 있다.

---

비재귀적으로 퀵 정렬 구현

  static void quickSort(int[] a , int left , int right){
        Stack<Integer> lstack = new Stack<>();
        Stack<Integer> rstack = new Stack<>();

        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);
            }
        }
    }

재귀호출을 통하여 구현할 경우 재귀 호출이 일어나면서 매개변수로 값들이 전달된다. 그러나 재귀를 사용하지 않을 경우는 작업이 끝나지 않은 부분에 대해서는 임시로 저장할 곳이 필요하다. 그렇기에 스택을 사용했다.

 

스택의 특성은 FILO방식으로 데이터를 입출력하게 되는데 이 부분에서 재귀호출과 JVM에서 메서드 호출 시 스택영역에 쌓이는 부분을 함께 생각해보면 쉽게 연상할 수 있다. 그리고 분할작업 시 가장 앞쪽과 뒤쪽부터하여 피벗을 기준으로 정렬을 수행하기에 이 시작,끝 인덱스를 저장하면 된다.

---

스택의 크기는 어떻게 할 것인가?

스택에는 아직 끝나지 않은 정렬에 시작,끝 인덱스를 저장한다고 했다. 그렇기에 분할이 많이 발생할 수록 스텍에는 계속 쌓이게 될 것이다.

이 부분을 그림을 통하여 확인해보자.

방법 1. 요솟수가 많은 그룹을 먼저 푸시하는 경우

Do it 자료구조와 함께 배우는 알고리즘 입문

방법 2. 요솟수가 적은 그룹을 먼저 푸시하는 경우

Do it 자료구조와 함께 배우는 알고리즘 입문

위 그림과 같이 요솟수가 큰 그룹 / 요솟수가 작은 그룹 둘 중 어느 것을 택하는지에 따라 스택에 다르게 쌓이는 것을 확인할 수 있다. 최종적으로 스택에 push/pop하는 횟수는 같다. 그러나 스택에 최대로 쌓이는 수에는 차이가 있다. 당연히 요솟수가 적을수록 적은 횟수로 분할을 종료할 수 있다. 그렇기에 방법1과 같이 요솟수가 적은 그룹을 먼저 분할하면(=요솟수가 큰 것부터 푸시) 스택에 동시에 쌓이는 데이터의 최대 개수를 줄일 수 있다. 

 

다음과 같이 방법1은 실제 배열의 요솟수가 n라고 했을 경우 스택에 쌓이는 최대 데이터는 log n보다 적게된다. 예를들어 n = 100만개일 때

대략 log 1000000 = 20이 된다.

 

이 부분을 보충하면 실제 밑수는 2이며 2^10 = 1024(대략 1000)이다. 그럼 1000^2 = 1000000이며 log 2^(10*2)은 대략 20이 나온다.

---

피벗은 어떻게 설정할 것인가?

퀵 정렬은 피벗을 기준으로 좌우로 교환이 이루어진다. 그렇기에 피벗을 어떻게 설정하냐가 전체적인 퀵 정렬 알고리즘의 성능에 영향을 미친다.

정렬을 빠르게 수행하기 위해서는 중앙 값을 피벗으로 설정하는게 가장 효율적이다. 중앙 값을 설정하면 배열이 고르게 절반으로 나누어지기 때문이다. 이 부분은 생각해보면 좌우로 중앙 값을 기준으로 비교하고 교환하기에 중앙 값은 최종적으로 중앙에 위치하게 되고 이를 기준으로 분할이 이루어진다.

그러나 중앙 값을 구하기 위해서는 별도의 작업을 필요로하며, 그에따른 비용도 발생한다.

방법1) 나눌 배열의 요솟수가 3개이상 시 임의의 3개의 요소를 선택하고 중앙 값인 요소를 피벗으로 선택

방법2) 방법1을 개선한 것으로 다음 단계를 따른다.

1. 나눌 배열의 처음, 가운데, 끝 요소를 먼저 정렬한다.
2. 정렬 후 중앙요소와 끝에서 두번째 요소를 교환한다.
3. 교환 후 끝에서 두번째 요소 값(a[right-1])를 피벗으로 한다.
4. 나눌 대상의 범위를 a[left+1]~a[right-2]로 좁힌다. -> 시작점인 left(=0)는 이미 피벗보다 작고 끝 점인 right는 더 크며 right -1은 현재 피벗이다.

이처럼 정렬이 완료될 때까지 위와 같은 단계를 반복 수행한다.

   //교환하는 메서드
    static void swap(int[] a, int idx1 , int idx2){
        int t = a[idx1]; a[idx1] = a[idx2] ; a[idx2] = t;
    }
    // 처음,중간,마지막 요소 정렬 메서드
    static int sort3elem(int[] x, int a, int b , int c){
        if(x[b] < x[a]) swap(x,a,b);
        if(x[c] < x[b]) swap(x,b,c);
        if(x[b] < x[a]) swap(x,a,b);
        return b;//중간 요소 인덱스, 중간요소 값 반환아님
    }
    // 퀵 정렬 메서드
    static void quickSort(int[] a , int left, int right){
        // 1.처음,중간,마지막 요소 정렬
        int pl = left;
        int pr = right;
        int m = sort3elem(a,left,(left+right)/2,right);

        // 2,3.피벗설정 및 중간요소와 마지막에서 두번째 교환
        int x= a[m];
        swap(a,m,right-1);

        // 4.범위를 시작 + 1 , 끝 -2로 지정
        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);
    }