정렬(2)

시간 복잡도가 O(N*log₂N)인 정렬 방법을 정리합니다.

• 퀵 정렬
• 병합 정렬
• 힙 정렬

퀵 정렬

Divide & Conquer 알고리즘.

최악의 경우 속도가 O(N²)가 될 수 있다.(정렬된 데이터에 pivot을 맨 우측으로 잡을 경우)

재귀 전 작업 때문에 재귀 오버헤드가 크다.

1. 배열의 한 원소를 고른다. (pivot이라고 부른다)
2. pivot보다 작은 원소는 pivot의 왼쪽으로, 큰 요소는 오른쪽으로 옮긴다.
3. pivot의 왼쪽 배열과 오른쪽 배열을 다시 1, 2 과정을 거치게 한다.
4. 배열의 크기가 0이나 1이 될때까지 반복한다.

void Quick_sort(int ary[], int low, int high) {
    if (low < high) {
        int pivot = Partition(ary, low, high);
        Quick_sort(ary, low, pivot - 1);
        Quick_sort(ary, pivot + 1, high);
    }
}
int Partition(int ary[], int low, int high) {
    int left = low, right = high;
    int pivot = ary[left];  // pivot을 가장 왼쪽으로 선택하기로 한다.
    while (left < right) {
        // pivot보다 큰 원소가 나올 때까지 left를 증가시킨다.
        while (ary[left] <= pivot)
            left++;
        // pivot보다 작은 원소가 나올 때까지 right를 감소시킨다.
        while (ary[right] > pivot)
            right--;
        if (left < right)
            swap(ary[left], ary[right]);
    }
    swap(ary[right], ary[low]);
    return right;
}

병합 정렬

공간복잡도가 O(N)이다. 공간이 더 필요하다.

퀵 정렬은 Big -> Small Scale로 정렬하지만, 병합 정렬은 Small -> Big Scale로 정렬하기 때문에 재귀 오버헤드가 없다.

결국에 하나씩 비교하기 때문에 입력 데이터의 사전 정렬에 영향을 받지 않는다.

1. 배열을 크기가 1이 될 때 까지 반으로 나눈다.
2. 반으로 나뉘어진 배열을 비교하면서 합친다.

void Merge_sort(int ary[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        Merge_sort(ary, left, mid);
        Merge_sort(ary, mid + 1, right);
        Merge(ary, left, mid, right);
    }
}
void Merge(int ary[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    int temp[SIZE];
    while (i <= mid && j <= right) {
        if (ary[i] <= ary[j])
            temp[k++] = ary[i++];
        else
            temp[k++] = ary[j++];
    }
    if (i > mid) {
        for (int l = j; l <= right; l++)
            temp[k++] = ary[l];
    } else {
        for (int l = i; l <= mid; l++)
            temp[k++] = ary[l];
    }
    for (int l = left; l <= right; l++)
        ary[l] = temp[l];
}

힙 정렬

우선순위 큐를 이용한 정렬 방법이다.

하나의 삽입, 삭제 과정이 O(logN)의 시간이 걸린다.

전체 데이터 삽입, 삭제 과정은 O(NlogN)의 시간이 걸린다.

정렬(1)

시간 복잡도가 O(N²)인 정렬 방법을 정리합니다.

• 버블 정렬
• 선택 정렬
• 삽입 정렬

버블 정렬

• 공간 복잡도 : O(1)

가장 큰 원소를 맨 뒤로 보내고 그 다음 원소를 그 앞, ... 을 반복한다.

void Bubble_sort(int ary[], int length) {
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length - 1 - i; j++) {
            if (ary[j] > ary[j + 1])
                swap(ary[j], ary[j + 1]);
        }
    }
}

개선된 버블 정렬 알고리즘이 있다. 두번째 for문에서 모두 정렬된 상태면 더 이상 살피지 않고 끝낸다.

void Bubble_sort_improved(int ary[], int length) {
    bool sorted = false;
    for (int i = 0; i < length; i++) {
        // 정렬된 상태
        if (sorted)
            break;
        sorted = true;
        for (int j = 0; j < length - 1 - i; j++) {
            if (ary[j] > ary[j + 1]) {
                // 정렬되지 않았으니 False 처리.
                sorted = false;
                swap(ary[j], ary[j + 1]);
            }
        }
    }
}

선택 정렬

• 공간 복잡도 : O(1)

가장 작은 원소를 맨 앞으로 보내고, 그 다음 원소를 그 다음으로 보낸다. 가장 작은 원소의 index를 저장해뒀다가 한번 훑은 뒤 swap을 하기 때문에 버블 정렬보다는 빠르게 가능하다.

void Selection_sort(int ary[], int length) {
    int min_index;
    for (int i = 0; i < length - 1; i++) {
        min_index = i;
        for (int j = i + 1; j < length; j++) {
            if (ary[min_index] > ary[j]) {![Image](https://i.imgur.com/jmdyU4f.png)
                min_index = j;
            }
        }
        swap(ary[i], ary[min_index]);
    }
}

삽입 정렬

• 공간 복잡도 : O(1)

두번째 원소부터 시작해서 왼쪽에 있는 원소와 비교한다. 왼쪽의 원소가 기준값보다 더 크면 오른쪽으로 보낸다. 왼쪽의 원소가 더 작거나(올바른 순서로 되어있거나) 배열의 맨 앞까지 오면 멈춘다.
데이터가 이미 어느정도 정리되어 있는 경우 유리하다.
루프 중간에 멈춰도 검사하지 않은 기존 데이터의 순서가 유지되어 안정적이다.

void Insertion_sort(int ary[], int length) {
    int i, j, current;
    for (i = 1; i < length; i++) {
        current = ary[i];
        for (j = i - 1; j >= 0 && ary[j] > current; j--) {
            ary[j + 1] = ary[j];
        }
        ary[j + 1] = current;
    }
}