퀵정렬

퀵정렬은 요솟수가 많은 배열을 정렬하는 경우 효과적이다. O(n log n) ~ O(n²)의 시간복잡도를 가진다.

재귀적인 퀵 정렬 구현

 

left < pr, pl < right 는 모두 그룹의 요솟수가 1개일때는 성립하지 않는 조건임.

이 조건은 요솟수가 2개 이상인 그룹을 나눌 때 필요하다.

 

import java.util.Scanner;

public class QuickSort {

    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    // 나눌 구간의 맨 앞 요소(left), 맨 뒤 요소(right)
    static void quickSort(int[] a ,int left, int right){
        int pl = left;
        int pr = right;
        int x = a[(pl+pr)/2]; // 피벗

        System.out.printf("a[%d]~a[%d]: {",left,right);
        for (int i = left; i < right; i++)
            System.out.printf("%d , ",a[i]);
        System.out.printf("%d}\n",a[right]);

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

    public static void main(String[] args) {
        System.out.println("배열을 나눕니다");
        System.out.println("요솟수: 9 ");
        int nx = 9;
        int[] x = new int[]{5,8,4,2,6,1,3,9,7};

        quickSort(x,0, nx-1);

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

    }
}

 

비재귀적인 퀵 정렬 구현

 

import java.util.Stack;

public class QuickSortV2 {
    // 비재귀버전 퀵 정렬

    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    // 나눌 구간의 맨 앞 요소(left), 맨 뒤 요소(right)
    static void quickSort(int[] a ,int left, int right){
        Stack<Integer> lstack = new Stack<>(); // int형 스택
        Stack<Integer> rstack = new Stack<>(); // int형 스택

        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]; // 피벗

            System.out.printf("a[%d]~a[%d]: {",left,right);
            for (int i = left; i < right; i++)
                System.out.printf("%d , ",a[i]);
            System.out.printf("%d}\n",a[right]);

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

        }
        
    }

    public static void main(String[] args) {
        System.out.println("배열을 나눕니다");
        System.out.println("요솟수: 9 ");
        int nx = 9;
        int[] x = new int[]{5,8,4,2,6,1,3,9,7};

        quickSort(x,0, nx-1);

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

    }
}

 

스택의 크기 구하기

요솟수가 많은 그룹을 먼저 stack에 푸시하면 

요솟수가 적은 그룹을 먼저 푸시하는것보다 스택에 동시에 쌓이는 데이터의 최대 개수가 적어진다. 

(요솟수가 적은 배열일수록 적은 횟수로 분할을 종료함)

요솟수가 n개라면 스택의 용량은 log n보다 작다.

 

피벗 선택하기

중앙값이 적절하나, 중앙값을 구하려면 별도의 처리와 시간이 요구된다.

따라서 다음과 같은 방법을 적용함

• 첫요소,가운데요소,끝요소를 정렬한다
• 가운데요소와 끝에서 두번째 요소를 교환한다 그리고 끝에서 두번째 요소(가운데요소였던것)를 피벗으로 한다.
• a[left]는 피벗 이하의 값, a[right-1], a[right]는 피벗 이상의 값이다.

적용시 나눌 대상의 범위가 줄어든다. 이렇게 하면 몇 퍼센트 더 빠른 속도로 정렬 가능.

왼쪽 커서 pl 시작위치 : left + 1

오른쪽 커서 pr 시작위치 : right - 2

 

import java.util.Stack;

public class QuickSortV3 {
    // 퀵 정렬(피벗개선버전)

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

    // x[a],x[b],x[c]를 정렬(가운데 값의 인덱스 반환)
    static int sort3elem(int[] x, int a, int b, int c){
        if(x[b] < x[a]) swap(x,b,a);
        if(x[c] < x[b]) swap(x,c,b);
        if(x[b] < x[a]) swap(x,b,a);
        return b;
    }

    // 나눌 구간의 맨 앞 요소(left), 맨 뒤 요소(right)
    static void quickSort(int[] a ,int left, int right){
        int pl = left;
        int pr = right;
        int m = sort3elem(a, pl, (pl+pr)/2, pr); // 처음, 가운데, 끝요소 정렬
        int x = a[m]; // 피벗

        swap(a,m,right-1); // 가운데<->끝에서두번째요소
        pl++;
        pr -= 2;


        System.out.printf("a[%d]~a[%d]: {",left,right);
        for (int i = left; i < right; i++)
            System.out.printf("%d , ",a[i]);
        System.out.printf("%d}\n",a[right]);

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

    }

    public static void main(String[] args) {
        System.out.println("배열을 나눕니다");
        System.out.println("요솟수: 9 ");
        int nx = 9;
        int[] x = new int[]{5,8,4,2,6,1,3,9,7};

        quickSort(x,0, nx-1);

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

    }
}

 

---

Arrays.sort를 이용한 퀵정렬

기본타입 정렬. 안정적이지 않은 정렬임.

import java.util.Arrays;

public class QuickSortForArrays {


    public static void main(String[] args) {
        System.out.println("배열을 나눕니다");
        System.out.println("요솟수: 7 ");
        int nx = 7;
        int[] x = new int[]{6,4,3,7,1,9,8};

        Arrays.sort(x);

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

    }
}