기본 정렬 알고리즘 (Sorting Algorithm)

정렬(Sorting)이란?

정렬은 원소(element)들을 일정한 기준을 통해 순서대로 나열하는 것이다.

정렬은 탐색(Search), 병합(Merge) 등 정렬된 상태에서 올바르게 동작하는 다른 알고리즘을 최적화하는 데 중요한 역할을 한다. 

정렬 알고리즘은 이러한 정렬을 진행하는 방식을 정의한 알고리즘을 말한다. 이번 포스팅에서는 기본적인 정렬 알고리즘 5가지에 대해 알아보자.

최악의 경우 (Worst case)

Worst case는 정렬 알고리즘에 대해 일반적으로 시간복잡도에 대한 최악의 경우는 그 알고리즘이 최대 실행시간으로 동작하는 경우를 말한다. 공간 복잡도에 대해서는 알고리즘이 최대 메모리를 사용하며 동작하는 경우를 의미한다.

안정성 (Stability)

정렬 알고리즘이 안전성을 가진다는 것은 동일한 정렬 Key를 가진 원소들의 상대적 순서가 보존됨을 의미한다. 예를 들어 (3, 5), (3, 8) 두 원소가 존재하는 배열에서 정렬을 수행할 경우 정렬 전에 (3, 8)이 (3, 5) 뒤에 있었다면 정렬 후에도 이 순서가 보존됨을 의미한다.

 

선택 정렬 (Selection Sort)

선택 정렬은 다음과 같은 순서로 동작한다.

① 정렬되지 않은 부분들 중 최솟값을 찾는다.

② 정렬되지 않은 부분의 맨 앞 인덱스의 값과 최솟값을 교체한다.

③ 모든 인덱스가 정렬될 때까지 해당 과정을 반복한다.

시간복잡도 : O(N^2)

선택 정렬은 리스트 전체에서 최솟값을 탐색하고, 최솟값을 탐색할 때마다 하나의 원소가 정렬되므로 전체 리스트에 대해서는 N번의 최솟값 탐색이 필요하다. 따라서 시간복잡도는 O(N^2)이다. (N은 리스트의 크기이다)

이는 최악의 경우에도 동일하다.

공간복잡도 : O(N)

선택 정렬은 리스트 하나를 사용하므로, O(N)이다.

구현 코드

void selection_sort(vector<int> input) {
    //input vector : 7, 3, 5, 4, 2, 1, 0, 6
    for (int i = 0; i < input.size(); i++) {
        //i는 지금까지 정렬된 인덱스를 의미한다. 
        //minidx는 최솟값이 존재하는 인덱스를 담을 변수이다.
        int minidx = i;
        for (int j = i + 1; j < input.size(); j++) {
            //정렬되지 않은 인덱스들 중 최솟값이 존재하는 인덱스를 찾는다.
            if (input[j] < input[minidx]) minidx = j;
        }
        //찾은 최솟값을 정렬되지 않은 인덱스의 맨 앞, 즉 i번째 원소와 교체한다.
        swap(input[i], input[minidx]);
    }
 
    printf("[Result of Selection Sort]\n");
    for (int i = 0; i < input.size(); i++) printf("%d ", input[i]);
    printf("\n");
}

선택 정렬은 알고리즘 자체가 단순하지만 시간복잡도가 O(N^2)인 만큼 리스트의 크기가 클 때 사용하기 적합하지 않다. 따라서 정렬할 리스트의 크기가 작을 때 효과적이다.

 

삽입 정렬 (Insertion Sort)

삽입 정렬은 리스트의 모든 원소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여, 해당 원소의 위치를 찾아 삽입하는 정렬 알고리즘이다.

삽입 정렬은 다음과 같이 동작한다.

① 정렬되지 않은 인덱스들 중 제일 앞 원소를 선택한다.

② 리스트의 정렬된 부분에 대해, 선택한 원소의 위치를 찾아 교체한다.

시간복잡도 : O(N^2)

리스트의 정렬된 부분에서 하나의 원소에 대한 위치를 찾을 때마다 정렬된 부분을 검색해야 하기 때문에, 시간복잡도는 O(N^2)이다.

공간복잡도 : O(N)

삽입 정렬은 리스트 하나를 사용하므로, O(N)이다.

구현 코드

void insertion_sort(vector<int> input) {
    //input vector : 7, 3, 5, 4, 2, 1, 0, 6
    for (int i = 1; i < input.size(); i++) {
        //1번 인덱스부터 시작 (0번 인덱스는 정렬되었다고 가정)
        int target = input[i], j = i - 1;
        while (j >= 0 && target < input[j]) {
            swap(input[j], input[j + 1]);
            j--;
        }
        input[j + 1] = target;
    }
 
    printf("[Result of Insertion Sort]\n");
    for (int i = 0; i < input.size(); i++) printf("%d ", input[i]);
    printf("\n");
}

 

버블 정렬 (Bubble Sort)

버블 정렬은 두 인접한 원소를 검사해 정렬하는 방법이다. 이 과정을 리스트 전체에 대해 한 사이클 반복하면, 오름차순 기준으로 가장 큰 값이 맨 오른쪽으로 가게 된다.

이 사이클을 전체 리스트 크기만큼 반복하면 전체 리스트가 정렬된다.

시간복잡도 : O(N^2)

리스트를 두 번 순회하기 때문에 시간복잡도는 O(N^2)이다.

공간복잡도 : O(N)

리스트 하나를 사용하므로, O(N)이다.

구현 코드

void bubble_sort(vector<int> input) {
    //input vector : 7, 3, 5, 4, 2, 1, 0, 6
    for (int i = 0; i < input.size() - 1; i++) 
        for (int j = 1; j < input.size() - i; j++)
            if (input[j - 1] > input[j]) swap(input[j - 1], input[j]);
 
    printf("[Result of Bubble Sort]\n");
    for (int i = 0; i < input.size(); i++) printf("%d ", input[i]);
    printf("\n");
}

 

 

병합 정렬 (Merge Sort)

병합 정렬(합병 정렬이라고도 한다.)은 분할 정복 기법을 사용한 정렬 알고리즘으로, 리스트를 쪼개어 사용한다.

정렬 알고리즘의 과정은 다음과 같다.

시간복잡도 : O(NlogN)

리스트를 한 번 쪼갤 때마다 n의 거듭제곱만큼 분할된 리스트가 늘어나므로, 정렬 시간은 NlogN이다.

공간복잡도 : O(N)

리스트를 쪼개어 사용하지만, 쪼갠 리스트를 모두 합하면 결국 원래의 리스트가 되므로 크기에 변화는 없다.

구현 코드

그림으로 설명된 병합 정렬은 Bottom-Up 방식이지만, 실제 구현은 Top-Down인 재귀 방식을 이용하면 더 쉽게 구현할 수 있다.

void merge(vector<int>& input, int start ,int end) {
    vector<int> temp;
    int mid = (start + end) / 2;
 
    //i는 왼쪽 부분 리스트의 맨 왼쪽을 가리키며, j는 오른쪽 부분 리스트의 맨 왼쪽을 가리킨다.
    int i = start, j = mid + 1;
 
    //i, j가 각각 가리키는 원소를 비교해 더 작은 값을 먼저 기록한다.
    while (i <= mid && j <= end) {
        if (input[i] < input[j]) temp.push_back(input[i++]);
        else temp.push_back(input[j++]);
    }
 
    //어느 한쪽이 먼저 모두 기록되었다면, 나머지 부분의 남은 원소를 모두 기록한다.
    while(i <= mid) temp.push_back(input[i++]);
    while (j <= end) temp.push_back(input[j++]);
 
    //원본 리스트를 병합 결과로 갱신한다.
    for (int i = 0; i < temp.size(); i++) {
        input[i + start] = temp[i];
    }
}
 
void merge_sort(vector<int>& input, int start, int end) {
    //input vector : 7, 3, 5, 4, 2, 1, 0, 6
    //최초 호출 시 start = 0, end = input.size() - 1임.
 
    //원소가 하나뿐인 리스트는 이미 정렬된 것으로 간주
    if (start == end) return;
 
    //현재 리스트를 반으로 나눠 각각 재귀호출
    int mid = (start + end) / 2;
    merge_sort(input, start, mid);
    merge_sort(input, mid + 1, end);
 
    //분할한 두 부분에 대한 재귀호출이 완료되면, 각각 정렬된 상태가 된다.
    //이를 merge함수로 병합 정렬한다.
    merge(input, start, end);
}

 

퀵 정렬 (Quick Sort)

퀵 정렬 역시 분할 정복 방법을 통해 리스트를 정렬한다.

Pivot값은 무작위로 선정할 수도 있다.

이 때, Pivot보다 작은 값은 모두 Pivot의 왼쪽에 위치하게 되고, Pivot보다 큰 값은 모두 Pivot의 오른쪽에 위치하게 된다.

한 피봇 당 최소 하나의 원소(Arr[Pivot])의 위치가 결정되므로, 이를 반복하다 보면 반드시 정렬을 마칠 수 있다.

시간복잡도 : O(nlogn), 단 최악의 경우 O(N^2)

공간복잡도 : O(N)

 

구현 코드

void quick_sort(vector<int>& input, int start, int end) {
    int left = start, right = end;
    if (start < end) {
        //최초 pivot을 start로 둔다.
        int pivot = input[start];
        //right이 left와 만날 때까지 반복한다.
        while (left < right) {
            while (input[right] >= pivot && left < right) right--;
            while (input[left] <= pivot && left < right) left++;
            if (left < right) swap(input[left], input[right]);
        }
        //pivot을 갱신한다.
        swap(input[start], input[left]);
        //리스트를 두 부분으로 나누어 재귀실행한다.
        quick_sort(input, start, left - 1);
        quick_sort(input, left + 1, end);
    }
}