[정렬 알고리즘] 퀵 정렬

퀵 정렬(quick sort)

퀵 정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하며 모든 그룹이 1명이 되면 정렬 완료

피벗은 그룹을 나누는 기준

 

■ 배열을 두개의 그룹으로 나누는 프로그램

피벗(x)을 설정 후, 왼쪽 끝 요소의 인덱스를 pl, 오른쪽 끝 요소의 인덱스를 pr

그룹을 나누기 위해서는 피벗 이하의 요소를 왼쪽 배열로, 이상의 요소를 오른쪽 배열로 옮겨야 한다.

- a[pl] >= 피벗(x)가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔

- a[pr] <= 피벗(x)가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔

스캔을 진행하다보면 두 커서(pl과 pr)이 교차가 되고, 이때 그룹을 나누는 과정이 끝나게 된다.

public class Partition {

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

    //배열울 나눈다 - 배열의 가운데 요소를 피벗으로 설정한다.
    static void partition(int[] a) {
        int n = a.length;
        int pl = 0;       //왼쪽 커서
        int pr = n - 1;   //오른쪽 커서
        int x = a[n / 2]; //피벗

        //피벗 x를 기준으로 두 그룹으로 나눔
        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.printf(a[i] + " ");
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 8, 7, 4, 5, 2, 6, 3, 10, 11};
        partition(a);
    }
}

■ 퀵 정렬

요소의 개수가 1개인 그룹은 더 이상 그룹을 나눌 필요가 없으므로 요소의 개수가 2개 이상인 그룹만 나누는 작업을 반복한다.

1. pr이 a[0]보다 오른쪽에 있으면(left < pr)  왼쪽 그룹을 나눈다.

2. pl이 a[배열의 마지막 요소의 커서]보다 왼쪽에 있으면(pl < right) 오른쪽 그룹을 나눈다.

import java.util.Arrays;

public class QuickSort {
    static void swap(int[] a, int idx1, int idx2){
        int tmp = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = tmp;
    }

    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) {
        int[] a = {5, 8, 4, 2, 6, 1, 3, 9, 7};
        quickSort(a, 0, a.length-1);

        System.out.println("quick sort : " + Arrays.toString(a));
    }
}