(알고리즘) 정렬 (3) - 퀵정렬

퀵 정렬이란?

풀기 힘든 문제를 풀기 쉽게 작은 단위로 점점 더 쪼개서 정렬을 수행하는 알고리즘

작은 단위로 쪼개는 과정은 파티셔닝을 통해 이루어진다.

 

기준되는 값을 하나 정해서 큰 값은 우측 작은 값은 좌측으로 정렬하면서 해당 작업이 끝나면 기준값을 기준으로 

좌측 우측의 기준값을 또다시 설정하여 해당 과정을 반복하여 결국은 정렬이 이루어지는 알고리즘이다.

---

아래를 예시로 해당 알고리즘을 설명해보자

 

기준값을 기준으로 나누기

현재 배열의 길이는 9이다.

pl을 왼쪽 커서 pr을 왼쪽 커서라고 지칭하겠다.

또한 기준값은 배열의 절반이라고 명시한다.

 

 

1. pl, pr, 기준값 설정

 

 

2. pl이 기준값보다 클 때까지 계속 전진! pr은 기준값보다 작을 때까지 계속 전진!

현재 pl은 8을 만났고 pr은 3을 만났으므로 stop!

 

 

3. 해당 값을 바꾸기

 

 

4. 또다시 전진! 현재 pl은 7을 만났고 pr은 2를 만났으므로 stop!

 

 

5. 해당 값 바꾸기

 

 

6. 또다시 전진! 기준값인 5로 pl, pr이 만나버렸다.

 

 

7. 그래도 다시 전진!

우리의 해당 정렬을 pr이 pl 보다 작을 때까지만 수행하기에 정렬을 종료한다.

 

코드 구현

public class QuickSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("배열을 나눕니다...");
        System.out.println("요솟수 : ");
        int nx = sc.nextInt();

        int[] array = new int[nx];

        for (int i=0 ; i<nx ; i++) {
            System.out.print("x["+i+"] = ");
            array[i] = sc.nextInt();
        }

        partition(array, nx);
    }

    private static void partition(int[] array, int length) {
        int pl = 0;
        int pr = length-1;
        int x = array[length/2];

        do {
            while (array[pl] < x) pl++;
            while (array[pr] > x) pr--;

            System.out.println("pl "+pl);
            System.out.println("pr "+pr);

            if (pl <= pr) 
                swap(array, pl++, pr--);

        }while (pl <= pr);

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

        System.out.println("pl "+pl);
        System.out.println("pr "+pr);

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

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

        System.out.println("피벗 이상의 그룹");
        for (int i=pr+1 ; i<length ; i++)
            System.out.print(array[i]+ " ");
        System.out.println();

    }
    static void swap(int[] array, int idx1, int idx2) {
        int temp = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = temp;
    }
}

---

퀵 정렬 알고리즘의 완성

위의 코드에 특정 조건을 추가해서 재귀로 변형하면 퀵 정렬이 완성된다.

이때 그룹의 개수가 1개일 경우에는 더 이상 쪼개지 않는다. 

 

 

코드 구현

public class QuickSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("배열을 나눕니다...");
        System.out.println("요솟수 : ");
        int nx = sc.nextInt();

        int[] array = new int[nx];

        for (int i=0 ; i<nx ; i++) {
            System.out.print("x["+i+"] = ");
            array[i] = sc.nextInt();
        }

        partition(array, 0, nx-1);

        for (int i=0 ; i<nx ; i++) {
            System.out.printf("x["+i+"] = "+ array[i]+ " ");
        }
    }

    private static void partition(int[] array, int left, int right) {
        int pl = left;
        int pr = right;
        int x = array[(pl+pr)/2];

        do {
            while (array[pl] < x) pl++;
            while (array[pr] > x) pr--;

            if (pl <= pr)
                swap(array, pl++, pr--);

        }while (pl <= pr);

        if (left < pr)
            partition(array, left, pr);
        if (pl < right)
            partition(array, pl, right);

    }
    static void swap(int[] array, int idx1, int idx2) {
        int temp = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = temp;
    }
}

---

Code Link

https://github.com/mike6321/PURE_JAVA/tree/master/Algorithm

mike6321/PURE_JAVA