정렬 -2

1. 퀵 정렬 

퀵 정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹이 1명이 되면 정렬을 마친다.

5 (pl)

7

1

4

6 (pivot)

2

3

9

8 (pr)

1. a[pl] >= x 가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔합니다.

2. a[pr] <=x 가 성립하는 요소를 찾을 때 까지 pr을 왼쪽으로 스캔합니다.

 

피벗 이하의 그룹 : a[0], ... , a[pl-1]

피벗 이상의 그룹 : a[pr+1] , .... a[n-1]

 

- 피벗과 일치하는 값을 가지는 그룹이 만들어 질 때

피벗과 일치하는 값을 가지는 그룹 a[pr+1], ... , a[pl-1] 

 

<배열을 나누는 프로그램>

static void partition(int[] a, int n) {
        int pl = 0;
        int pr = n - 1;
        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);
    }

 

위의 배열을 나누는 프로그램을 좀 더 발전시키면 퀵 정렬 알고리즘이 됩니다.

1. pr이 left보다 오른쪽에 있으면(= left < pr) →  왼쪽 그룹을 나눕니다.

2. pl이 right보다 왼쪽에 있으면(= pl < right) → 오른쪽 그룹을 나눕니다. 

→ left < pr , pl < right 은 모두 그룹의 개수가 1개인 경우에는 성립하지 않습니다.

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

 

2. 병합 정렬

정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다.

 

정렬을 마친 배열의 병합 : 시간복잡도 O(n)

static void merge(int[] a, int na, int[] b, int nb, int[]c) {
    int pa=0;
    int pb=0;
    int pc=0;
    
    while(pa < na && pb < nb)
        c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];
        
    while(pa<na)
        c[pc++] = a[pa++];
    while (pb<nb)
        c[pc++] = b[pb++];
    }

 

-병합 정렬 알고리즘의 순서

배열의 요소 개수가 2개 이상인 경우

1. 배열의 앞부분을 병합 정렬로 정렬합니다.

2. 배열의 뒷부분을 병합 정렬로 정렬합니다.

3. 배열의 앞부분과 뒷부분을 병합합니다.

 

static void _mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int i; // a 인덱스
            int center = (left + right) / 2;
            int p = 0; // buff에 복사하기 위한 인덱스, 복사한 길이
            int j = 0; // buff 인덱스
            int k = left;
 
            _mergeSort(a, left, center);
            _mergeSort(a, center + 1, right);
 
            for (i = left; i <= center; i++)
                buff[p++] = a[i];
 
            while (i <= right && j < p)
                a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
 
            while (j < p)
                a[k++] = buff[j++];
        }
    }
 
    static void mergeSort(int[] a, int n) {
        buff = new int[n]; // 작업용 배열을 생성
        _mergeSort(a, 0, n - 1); // 배열 전체를 병합 정렬
        buff = null; // 작업용 배열을 해제
    }

 

---

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 [시바타 보요, 옮긴이 : 강민 (이지스퍼블리싱)]