퀵(quick) 정렬

* 퀵 정렬

일반적으로 많이 사용되고 있는 아주 빠른 정렬 알고리즘.
어느 한 요소를 선택하는데 이를 피벗(pivot) 이라고 한다.
그 요소보다 작은 그룹과 큰 그룹을 나누고 각 그룹에서의 피벗 설정과 그룹 나눔을 반복하여 모든 그룹이 1개의 요소가 되면 정렬을 마친다.


1. 배열을 피벗으로 나누어보는 코드

//배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다.
static void swap(int[] a, int idx1, int idx2) {
    int t = a[idx1];
    a[idx1] = a[idx2];
    a[idx2] = t;
}

//배열을 나눕니다.
static void partition(int[] a, int n) {
    int pl = 0; //point left 왼쪽 커서
    int pr = n - 1; //point right 오른쪽 커서
    int x = a[n / 2]; //피벗(가운데 위치의 값)

    do {
        while (a[pl] < x) pl++; //왼쪽커서의 값이 피벗보다 작은경우 계속 검사
        while (a[pr] > x) pr--; //오른커서의 값이 피벗보다 큰경우 계속 검사
        if (pl <= pr)
            swap(a, pl++, pr--); // 스왑한다.
    } while (pl <= pr);

    System.out.println("피벗의 값은 " + x + "입니다.");

    System.out.println("피벗 이하의 그룹");
    for (int i = 0; i <= pl - 1; i++)
        System.out.print(a[i] + " ");
    System.out.println();

    if (pl > pr + 1) {
        System.out.println("피벗과 일치하는 그룹");
        for (int i = pr + 1; i <= pl - 1; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
    
    System.out.println("피벗 이상의 그룹");
    for (int i = pr + 1; i < n; i++)
        System.out.print(a[i] + " ");
    System.out.println();
}

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); //오른끝이 왼쪽커서보다 크면 오른그룹을 계속 나눈다.
}

3. 비재귀적으로 퀵소트를 구현 (스택)

    //비재귀버전
    static void quickSort2(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[(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) {
                // 왼쪽 그룹 범위의 인덱스를 푸시합니다.
                lstack.push(left);
                rstack.push(pr);
            }

            if (pl < right) {
                // 오른쪽 그룹 범위의 인덱스를 푸시합니다.
                lstack.push(pl);
                rstack.push(right);
            }
        }
    }