자료들의 비교 기반 정렬

이번 포스트에서는 자료간의 비교를 통한 정렬에 대해서 포스팅하도록 하겠습니다.

 

비교 기반 정렬

비교를 통해서 정렬을 하는 방법에는 크게 5가지가 있습니다.

1. 버블 정렬
2. 선택 정렬
3. 삽입 정렬
4. 합병 정렬
5. 퀵 정렬

이 외에도 이전 포스트에서 설명한 최대힙, 최소힙으로도 키 값의 오름차순, 내림차순을 부여할 수 있습니다.

 

버블 정렬

먼저 버블 정렬입니다. 버블 정렬은 리스트의 처음부터 끝까지 인접한 두 값의 순서가 맞지 않을 때, 교환하는 작업을 N-1 회 반복합니다. 따라서, 리스트의 처음부터 끝까지 검사하므로 N번, 그 반복문에서 N-1번 검사하기 때문에, 버블 정렬은 시간복잡도가 O(N^2)로 분석됩니다.

 

버블 정렬은 동일 키 값을 갖는 자료들의 순서가 정렬 후에도 유지되므로, stable 하다고 할 수 있습니다.

또한, O(1)의 추가 저장 공간만을 사용하여 정렬하기 때문에, In-place 정렬 방식입니다.

 

void bubbleSort(int* list, int N) {
    for(int i = N-1; i > 0; i--) {
        for(int k = 0; k < i; k++) {
            if(list[k] <= list[k+1])    continue;                    //순서가 맞으므로 교환X
            int t = list[k];
           list[k] = list[k+1];
           list[k+1] = t;
        }
    }
}

 

선택 정렬

다음은 선택 정렬입니다. 선택 정렬은 비어있는 정렬 리스트, 비정렬 리스트가 있을 때, 비정렬 리스트 내에서 최소값을 선택하여 정렬 리스트의 마지막 위치로 이동시키는 방법을 비정렬 리스트가 공백 리스트가 될때 까지 반복하는 정렬 방법입니다.

 

최소값을 탐색하는 과정에서 O(N), 그리고 탐색을 N-1 회 반복하기 때문에 선택 정렬도 O(N^2)로 분석됩니다.

 

한 리스트 안에서 구현이 가능하기 때문에 In-place하나, 위치가 바뀌기 때문에 stable 하지는 않습니다.

 

void selectionSort(int* list, int N) {
    for(int i = 0; i < N-1; i++) {
        int minIndex = i;
        for(int k = i + 1; k < N; k++)    if(list[k] < list[minIndex])    minIndex = k;            //최소값 
        int t = list[i];
        list[i] = list[minIndex];
        list[minIndex] = t;
    }
}

 

삽입 정렬

삽입 정렬은 비어있는 정렬 리스트와 비정렬 리스트가 있을 때, 비정렬 리스트의 앞에 정렬 리스트가 있다고 가정하고, 비정렬 리스트의 첫 위치 자료를 정렬 리스트 내 올바른 위치에 삽입하는 과정을 비정렬 리스트가 공백 리스트가 될 때까지 반복합니다.

 

삽입 정렬도 선택 정렬과 마찬가지로 O(N^2)의 시간복잡도가 소요되며, stable하고 In-place 방식입니다.

 

void insertionSort(int* list, int N) {
    for(int i = 1, j = 0; i < N; i++) {        //j가 정렬리스트 i가 비정렬리스트
        int key = list[i];
        for(j = i - 1; j >= 0 && key < list[j]; j--) list[j + 1] = list[j];        //비정렬리스트의 첫값이 정렬리스트에 삽입 될 때, 올바른 위치를 찾음.
        list[j + 1] = key;
    }
}

합병 정렬

합병 정렬은 비정렬 리스트를 분할정복 방식으로 정렬하는 방법입니다.

 

비정렬 리스트를 반으로 계속해서 나누어, 가장 작게 분할한 후 그 분할 된 리스트들 끼리 비교하여 정렬하고 합치는 방법입니다.

 

stable하지만, 정렬과정에서 리스트의 복사가 일어나므로, In-place 기법은 아닙니다.

시간복잡도는 트리 처럼 이진으로 분할하면서 진행하기 때문에 log n, 리스트를 복사하면서 n 소요되어 O(n log n)으로 분석됩니다.

 

void merge_list(int* list, int left1, int right1, int left2, int right2) {
    int* sorted = (int*)malloc(sizeof(int)*(right2 - left1 + 1));
    int i = left1, j = left2, k = 0;
    while(i <= right1 && j <= right2)    sorted[k++] = (list[i] < list[j]) ? list[i++] : list[j++];            //나눠진 리스트 들끼리 비교
    while(i <= right1)    sorted[k++] = list[i++];
    while(j <= right2)    sorted[k++] = list[j++];
    for(i = left1, k = 0; i <= right2; i++, k++)    list[i] = sorted[k];
    free(sorted);
}
 
void merge_sort(int* list, int left, int right) {
    if(left >= right)    return;
    int m = (left + right) / 2;
    merge_sort(list, left, m);                //반으로 리스트 분할
    merge_sort(list, m + 1, right);
    merge_list(list, left, m, m + 1, right;);                //
}

퀵 정렬

마지막으로 퀵 정렬은 비정렬 리스트 내에서 피봇값을 임의로 정한 후, 피봇값을 기준으로 피봇값보다 작은 수들의 리스트, 큰 수들의 리스트로 분할합니다. 이를 분할 정복방식으로 작게 쪼개고 다시 합병하는 방식을 거칩니다.

 

합병 정렬과는 반대로 값의 복사는 일어나지 않아서 In-place 기법이지만, stable하지는 않습니다.

피봇값을 기준으로 큰 리스트, 작은 리스트를 구분하면서 n, 이를 분할하고 정복하는 과정에서 log n이 소요되어 O(n log n)으로 분석됩니다.

 

단, 정렬된 리스트에서 퀵 정렬을 다시 수행한 케이스의 경우(최악의 경우) 피봇값이 제일 왼쪽에 고정되어 리스트의 끝까지 반복하므로, O(N^2)가 소요됩니다. 따라서 평균은 O(n log n)이나, 최악의 경우는 O(N^2)로 분석됩니다.

int partition(int* list, int low, int high) {
    int i = low, j = high + 1, pivot = list[low];
    while(1) {
        while(list[++i] < pivot)    if(i == high)    break;
        while(pivot < list[--j])    if(j == low)    break;
        if(j <= i)    break;
        int t = list[i]; list[i] = list[j]; list[j] = t;
    }
    int t = list[low]; list[low] = list[j]; list[j] = t;
    return j;
}
 
void quickSort(int* list, int low, int high) {
    if(high <= low)    return;
    int p = partition(list, low, high);
    quickSort(list, low, p-1);
    quickSort(list, p+1, high);
}

이렇게 비교 기반 정렬에 대해서 소개 드렸습니다.

 

다음 포스트에서는 그래프에 대한 내용을 포스트 하도록 하겠습니다.