[자료구조](8)[정렬 알고리즘 2]

머지 정렬 (merge sort)

배열을 쪼개서 정렬 -> 다시 합치며 정렬
예) 4 3 2 1 를 정렬한다면
    분할 1: (4 3) (2 1)
    분할 2: (4) (3) (2) (1)
    병합 1: (3 4) (1 2)
    병합 2: (1 2 3 4)

void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1; 
    int n2 = right - mid;    

    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));
    // 호출될 때마다 요소 개수가 바뀌므로 동적할당

    if (L == NULL || R == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }

    // L, R에 요소들 넣기
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 실제 정렬 부분
    i = 0; j = 0; k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    // L, R에 남아있는 요소들 다시 arr로 넣기
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    free(L);
    free(R);
}
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        // 재귀로 계속 절반으로 나눔
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

N개의 데이터를 logn만큼 쪼개고 n번 연산하므로,
최악, 평균, 최선일 때 O(nlogn)

 

퀵 정렬 (quick sort)

머지 정렬이랑 비슷한데 단순히 가운데를 쪼개는 게 아닌 pivot이라는 값 기준으로 쪼개기
예) 4 3 2 5 1 6 7 를 정렬한다면
    3을 pivot으로 잡는다면,
    4 |3| 2 5 1 6 7
    1 2 |3| 5 4 6 7
    이후 각각 1, 5를 pivot으로 잡으면
    (|1| 2) 3 (|5| 4 6 7)
    1 2 3 4 5 7 6 7
    -> 어짜피 N이 커지면 pivot은 아무거나 잡아도 성능에 영향 없음

 

재귀 이용한 퀵 정렬

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}
void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

 

스택 이용한 퀵 정렬: 재귀의 움직임을 쌩으로 스택으로 옮기면 된다.

void iterativeQuickSort(int arr[], int low, int high) {
    std::stack<int> stack;
    stack.push(low);
    stack.push(high);
    while (!stack.empty()) {       //재귀로 쪼갠거에서 반복으로 쪼개기
        high = stack.top(); stack.pop();
        low = stack.top(); stack.pop();
        int pivot = partition(arr, low, high);
        if (pivot - 1 > low) {
            stack.push(low);
            stack.push(pivot - 1);
        }
        if (pivot + 1 < high) {
            stack.push(pivot + 1);
            stack.push(high);
        }
    }
}

대부분은 머지 정렬과 비슷하겠으나, 만약 분할된 리스트가 한쪽 방향으로 쏠린다면

재귀호출로 인해 n-1배열을 n번 정렬한 것과 같아진다. 따라서
최악일 때 O(n^2)
평균, 최선일 때 O(nlogn)

 

머지 정렬보다 느릴 가능성이 존재하나 많이 쓰임
    추가 메모리 할당이 필요없어 머지정렬보다 공간을 덜 차지
    캐시 친화적이라 빠름

 

기수 정렬 (radix sort)

자릿수에 따라 큐를 사용해 정렬 (10진수라면 10개의 큐를 이용해 정렬)
예) 62 3 500 12 을 정렬하면
    1의 자리에 대해 각 큐에 넣기
    queue 0(500), queue 2(62, 12), queue 3(3)
    큐에서 순서대로 꺼내기
    500 62 12 3
    10의 자리에 대해 각 큐에 넣기
    queue 0(500, 3), queue 1(12), queue 6(62)
    큐에서 순서대로 꺼내기
    500 3 12 62
    100의 자리에 대해 각 큐에 넣기
    queue 0(3, 12, 62), queue 5(500)
    큐에서 순서대로 꺼내기
    3 12 62 500

void radix_sort(int arr[], int n) { //단, arr는 정수
    std::queue<int> buckets[10]; //0~9까지의 큐
    int maxVal = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > maxVal) maxVal = arr[i];
    int exp = 1;
    while (maxVal / exp > 0) { //가장 큰 값의 자릿수만큼 돌기
        for (int i = 0; i < n; i++) {
            int bucketIdx = (arr[i] / exp) % 10; //n의 자릿수 체크
            buckets[bucketIdx].push(arr[i]);     //해당 큐에 push
        }
        int index = 0;
        for (int i = 0; i < 10; i++) {
            while (!buckets[i].empty()) {
                arr[index++] = buckets[i].front(); //arr에 저장하고
                buckets[i].pop();                  //pop으로 제거
            }
        }
        exp *= 10;
    }
}

결국 자릿수마다 N개의 데이터를 큐에 넣었다 뺐다 하므로
O(dn) (d = 자릿수) <- 보통은 계수는 생략하는데 자릿수가 너무 중요해서 살림
꽤나 빠른 정렬이나 단점으로
    자료가 오직 정수형일 때만 가능함 (실수 안됨)
    큐 할당 때문에 공간을 많이 잡아먹음
    자릿수만큼 정렬해야 하므로 데이터의 범위 필요함.