[알고리즘-04] 정렬(Sorting) - 퀵 정렬, 병합 정렬, 힙 정렬

1. 퀵 정렬(Quick sort)

1) 퀵 정렬이란?

- 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘

- 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹이 1명이 되면 정렬을 마침

- 피벗(pivot) : 그룹을 나누는 기준이 되는 요소

- 시간복잡도는 O(n log n)

- 하지만 최악의 경우, O(n²)

 

 

2) 배열을 두 그룹으로 나누기

- x : 피벗

- pl : 왼쪽 끝 요소의 인덱스

- pr : 오른쪽 끝 요소의 인덱스

 

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

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

(3) a[pl]과 a[pr]의 값을 교환

(4) pl과 pr이 교차하면 두 그룹으로 나누어짐

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

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

 

+) pl > pr + 1인 경우에는 피벗과 일치하는 값을 가지는 그룹(a[pr+1], ... , a[pl-1])이 생길 수 있음

 

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

 

3) 정렬하기

- 요소의 개수가 2개 이상인 그룹을 아래처럼 배열을 반복해서 나눔

 

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

(2) pl이 a[n-1]보다 왼쪽에 있으면(pl < right) 오른쪽 그룹을 나눔

 

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


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);    
    
    // 여기서 각 그룹별로 다시 quick sort 수행
    if(left < pr) quickSort(a, left, pr);
    if(pl < right) quickSort(a, pl, right);
}

public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    int n = stdIn.nextInt();
    int[] x = new int[n];
    
    for(int i = 0; i < n; i++) {
        x[i] = stdIn.nextInt();
    }
    
    // 배열 x를 퀵 정렬
    quickSort(x, 0, n-1);
}

 

 

 

---

 

 

2. 병합 정렬(Merge sort)

1) 병합 정렬이란?

- 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 뒤 병합(merge)하는 작업을 반복하여 정렬을 수행하는 알고리즘

- 시간복잡도는 O(n log n)

 

2) 정렬을 마친 배열의 병합

- 각 배열에서 선택된 요소의 값을 비교하여 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복

- na : 배열1의 요소의 개수

- a : 배열1 (정렬됨)

- nb : 배열2의 요소의 개수

- b : 배열2 (정렬됨)

- c : 두 배열을 병합하여 저장할 새로운 배열

 

- pa, pb, pc : 각각 배열 a, b, c의 현재 인덱스

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++];
}
       

 

3) 병합 정렬

- '2) 정렬을 마친 배열의 병합'을 이용하여 분할 정복법에 따라 정렬하는 알고리즘

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

 (1) 배열의 앞부분을 병합 정렬로 정렬

 (2) 배열의 뒷부분을 병합 정렬로 정렬

 (3) 배열의 앞부분과 뒷부분을 병합

 

static int[] buff;	// 작업용 배열

// a[left] ~ a[right]를 재귀적으로 병합 정렬
// left가 right보다 작을 때 동작
static void __mergeSort(int[] a, int left, int right) {
    if(left < right) {
        int i;
        int center = (left + right) / 2;
        int p = 0;
        int j = 0;
        int k = left;
        
        __mergeSort(a, left, center);
        __mergeSort(a, center+1, right);
        
        // 배열의 앞부분을 buff에 복사
        for(i = left; i <= center; i++)
            buff[p++] = a[i];
        
        // 배열의 뒷부분과 buff로 복사한 배열의 앞부분 p개를 병합한 결과를 배열 a에 저장
        while(i <= right && j < p)
            a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
        
        // 배열 buff에 남아 있는 요소를 배열 a에 복사
        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;
}

 

 

 

 

---

 

 

 

3. 힙 정렬(Heap sort)

1) 힙 정렬이란?

- 힙(heap)을 사용하여 정렬하는 알고리즘

- 힙(heap) : '부모의 값이 자식의 값보다 항상 크다'를 만족하는 완전 이진트리

- 시간복잡도는 O(n log n) 

 

2) 힙의 요소 저장

- 다음과 같은 관계가 성립함

 (1) 부모 : a[(i-1) / 2]

 (2) 왼쪽 자식 : a[i*2 + 1]

 (3) 오른쪽 자식 : a[i*2 + 2]

 

3) 힙 정렬

- '가장 큰 값이 루트에 위치'하는 특징을 이용하는 정렬 알고리즘

- 힙에서 가장 큰 값인 루트를 꺼내는 작업을 반복하고 그 값을 늘어놓으면 배열은 정렬을 마치게 됨

- 선택 정렬을 응용한 알고리즘

- 루트를 꺼낸 뒤, 힙의 형태를 유지할 수 있도록 재구성해야 함

 

+) 루트를 없애고 힙 상태 유지하기

 (1) 루트를 꺼냄

 (2) 마지막 요소를 루트로 이동함

 (3) 자기보다 큰 값을 가지는 자식 요소와 자리를 바꾸며 아래쪽으로 내려가는 작업을 반복

  -> 자식의 값이 작거나 잎에 다다르면 작업 종료

 

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

// a[left] ~ a[right]를 힙으로 만듦
static void downHeap(int[] a, int left, int right) {
    int temp = a[left];  	// 루트
    int child;			 // 큰 값을 가진 노드
    int parent;			 // 부모
    
    for(parent = left; parent < (right + 1) / 2; parent = child) {
        int cl = parent * 2 + 1; 	 // 왼쪽 자식
        int cr = cl + 1;		  // 오른쪽 자식
        // 큰 값을 가진 노드를 자식에 대입
        child = (cr <= right && a[cr] > a[cl]) ? cr : cl;
        if(temp >= a[child])
            break;
        a[parent] = a[child];
    }
    
    a[parent] = temp;
}

// 힙 정렬
static void heapSort(int[] a, int n) {
    // a[i] ~ a[n-1]을 힙으로 만들기
    for(int i = (n-1)/2; i >= 0; i--)
        downHeap(a, i, n-1);
    
    
    for(int i = n-1; i > 0; i--) {
        // 가장 큰 요소와 아직 정렬되지 않은 부분의 마지막 요소를 교환
        swap(a, 0, i);
        // a[0] ~ a[i - 1]을 힙으로 만듦
        downHeap(a, 0, i-1);
    }
}

 

 

 

 

 

 

참고 - Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 (저자 : 보요 시바타, 출판 : 이지스 퍼블리싱)