[알고리즘] 02. 정렬(퀵 정렬, 병합정렬)

<본 포스팅은 개인 공부 목적으로 작성되었습니다.>

✅퀵 정렬(Quick sort)

퀵 정렬(Quick sort)은 Divide and Conquer(분할 정복) 전략을 활용하여 정렬을 해주는 알고리즘이다. 기준점(pivot)을 정해서 기준점보다 작으면 왼쪽, 크면 오른쪽 정렬하고 또 재귀를 통해 오른쪽, 왼쪽 배열을 동일한 방법으로 계속해서 정렬해 주면 된다.

출처 - https://en.wikipedia.org/wiki/Quicksort

이렇게 pivot을 하나 정해 정렬하면 pivot은 제대로 된 위치를 찾은 것이고 그럼 pivot을 제외하고 양쪽 배열의 pivot을 정해 계속 정렬해 나가는 알고리즘이다.

✔ 코드

#include <stdio.h>

void Quick(int *arr, int start, int end){
    if(start>=end){
        return;
    }

    int pivot = start;    // pivot은 항상 첫 번째 값으로
    int i = pivot+1;
    int j = end;
    int temp;

    while(i<=j){
        while(i<=end && arr[i]<=arr[pivot]){  // pivot값이 더 크면 바꿔줄 필요가 없으므로 i++
            i++;
        }
        while(j>start && arr[j]>=arr[pivot]){  // pivot값이 더 작으면 바꿔줄 필요가 없으므로 j--
            j--;
        }

        if(i>=j) break;  // i가 j 보다 커지는 순간 pivot을 기준으로 한 정렬이 완료

        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    temp = arr[j];
    arr[j] = arr[pivot];
    arr[pivot] = temp;

    Quick(arr, start, j-1);       // pivot을 기준으로 다시 왼쪽 정렬
    Quick(arr, j+1, end);      // pivot을 기준으로 다시 오른쪽 정렬

}

int main(){

    int i;
    int arr[10] = {5, 6, 10, 4, 3, 8, 7, 1, 2, 9};

    Quick(arr, 0, 9);

    for(i=0;i<10;++i){
        printf("%d ", arr[i]);
    }

    return 0;
}

pivot은 첫 번째 값으로 두고, i는 pivot+1, j는 end값으로 둔다. 그러고 나서 i가 j보다 작을 때까지 while문을 돈다. i 먼저 계산을 해주면 현재 i의 값인 6이 pivot의 값인 5보다 크므로 여전히 i는 1이고, j는 값이 9이므로 5보다 작을 때까지 j--해준다. 그러고 나면 i는 6을 j는 2를 가리키게 된다.

그러고 나면 이제 두 개의 값을 바꿔준다. 바꿔준 뒤 다시 같은 연산을 반복한다.

그러고 나면 i가 j보다 커지는 상황이 오는데 이렇게 되면 j를 기준으로 j의 오른쪽은 다 pivot보다 큰 값이 오게 되고 j를 포함한 j의 왼쪽으로는 pivot보다 작은 값이 오게 된다.

그러면 break를 해주어 j와 pivot값을 바꿔준다. 이제 원래 pivot값이었던 5를 기준으로 왼쪽으로는 5보다 작은 값이, 오른쪽으로는 5보다 큰 값이 오게 된다. 그러고 나서 재귀 함수로 이 상황을 반복해주면 오름차순으로 정렬이 된다.

✔ 장단점

장점

• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간이 필요하지 않는다.
• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(N logN)을 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.

단점

• 불안정 정렬이다.
• 이미 정렬된 배열일 경우 시간 복잡도는 O(N^2)이다.

✅병합 정렬(Merge sort)

병합 정렬(Merge sort)도 퀵 정렬(Quick sort)과 마찬가지로 Divide and Conquer(분할 정복) 전략을 활용하여 정렬을 해주는 알고리즘이다. 배열을 절반으로 나누고 재귀적으로 계속 절반으로 나눈 뒤 합쳐주면서(Merge) 정렬하는 방식의 알고리즘이다.

출처 - [https://en.wikipedia.org/wiki/Merge_sort] (https://en.wikipedia.org/wiki/Merge_sort)

이렇게 가장 작은 단위로 쪼갠 뒤 합쳐가면서 정렬해 주는 알고리즘이다.

✔ 코드

#include <iostream>

using namespace std;

void Merge(int* arr, int start, int end) {       // 쪼갠 배열을 합치면서 정렬하는 함수
    int i = start;                               // 왼쪽 배열
    int mid = (start + end) / 2 + 1;
    int j = mid;                                 // 오른쪽 배열
    int a[10];                                   // 임시배열
    int idx = start;                             // 임시배열의 index값

    while (i < mid && j <= end) {                // 쪼갰던 배열의 범위 만큼만 while문을 돈다.
        if (arr[i] <= arr[j]) a[idx++] = arr[i++];    // i가 j보다 작거나 같다면 a배열에 i값을 넣어주고 아니면 j값을 넣어준다.
        else a[idx++] = arr[j++];
    }

    while (i < mid) a[idx++] = arr[i++];         // 나머지 남은 값들은 이미 정렬되어있는 값이기 때문에 남은 값을 순서대로 넣어준다.
    while (j <= end) a[idx++] = arr[j++];

    for (int i = start; i <= end; i++) {         // 정렬된 a배열로 arr배열을 갱신해 준다.
        arr[i] = a[i];
    }
}

void MergeSort(int* arr, int start, int end) {      // 재귀호출로 쪼개주는 함수
    if (start == end) return;                       // start와 end가 같으면 값이 1개인 경우니까 return 해준다.
    MergeSort(arr, start, (start + end) / 2);       // 재귀호출을 통해 왼쪽으로 쪼갠다.
    MergeSort(arr, (start + end) / 2 + 1, end);     // 재귀호출을 통해 오른쪽으로 쪼갠다.
    Merge(arr, start, end);                         // 다 쪼개고 나면 Merge함수로 합쳐준다.
}

int main() {

    int arr[10] = { 5, 6, 10, 4, 3, 8, 7, 1, 2, 9 };

    MergeSort(arr, 0, 9);

    for (int i : arr) {
        cout << i << " ";
    }

    return 0;
}

재귀 호출을 통해 배열을 쪼개고 그다음 Merge함수를 통해 정렬을 해 주었다. 배열을 쪼갤 때는 물리적으로 직접 쪼개는 것이 아닌 index의 범위를 통해 논리적으로 쪼갠 뒤 정렬하면서 합쳐주었다.

✔ 장단점

장점

• 시간 복잡도가 항상 O(N logN)이다.
• 안정 정렬이다.

단점

• 배열로 구성하면 임시 배열이 필요하다.
  • 메모리 낭비를 초래한다.
  • 제자리에서 하는 정렬이 아니다.
• 레코드의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

 

참고자료

https://github.com/WooVictory/Ready-For-Tech-Interview/tree/master/Algorithm