[알고리즘] 정렬 알고리즘 정리

최근에 카카오, 라인 CS 필기 테스트를 보면서 기초 CS를 많이 까먹었음을 깨달았다..

퀵 정렬만 공부하고 갔다가, 다른 정렬들도 무수히 물어봐서 식은땀을 좀 흘렸다..;;;;;;;

기껏 어려운 1차 코딩테스트 다 붙었는데, CS 때문에 다 떨어지게 생겼다. 지금..

그래서 정렬 알고리즘부터 다시 정리해보기로! 했다.

정렬의 케이스별 성능 분석

정렬 알고리즘은 컴퓨터 공학에서 매우 중요한 문제 중 하나이다. 그리고 자주 써야 한다.

뭐 물론 라이브러리 호출해서 자주 쓰긴 하지만, 내부 구조를 이해해야 상황에 따라 적절하게 사용할 수 있다.

이번 포스트에서 살펴볼 정렬 알고리즘은 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬이다.

 

💡 버블 정렬(Bubble Sort)

버블 정렬은 거의 모든 상황에서 최악의 성능을 보여주지만, 이미 정렬된 자료에서는 1번만 순회하면 되기 때문에 최선의 성능을 보여주는 알고리즘이다. 이미 정렬되어 있는 데이터를 왜 정렬하냐는 의문이 들 수 있지만, 정렬 알고리즘은 데이터가 정렬되어있는지 모르고 수행되는 경우도 있기 때문에 이 경우도 고려해줘야 한다.

 

버블 정렬은 다음과 같은 순서로 작동한다.

1. 0번째 원소와 1번째 원소를 비교 후 정렬
2. 1번째 원소와 2번째 원소를 비교 후 정렬
...
3. n - 1번째 원소와 n번째 원소를 비교 후 정렬

완벽히 정렬될 때까지 최대 n번 위와 같은 순서로 순회한다.

한 번 순회할 때마다 마지막 하나가 정렬되므로 원소들이 거품이 올라오는 것처럼 보여서 버블 정렬이라고 부른다.

원리도 직관적이어서 구현하기 편하긴 하지만 꽤나 비효율적인 정렬 방식이다.

그래서 보통 처음 배울 때 한 번 짜보고 나면 실무에서 쓰는 경우는 잘 없다.

 

#include <stdio.h>
 
int main(void){
    int array[10] = {4, 5, 2, 7, 9, 1, 8, 3, 6, 10};
    int i, j, temp;
    
    for(i=0; i<10; i++){
        for(j=0; j<9-i; j++){
            if(array[j] > array[j+1]){
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }    
        }
    }
}

 

💡 선택 정렬(Selection Sort)

선택 정렬은 주어진 자료들 중에서 현재 위치에 맞는 자료를 찾아 선택하여 위치를 교환하는 정렬 알고리즘이다.

한 번 순회하고 나면 알고리즘 상 전체 자료 중 가장 작은 값의 자료가 0번째 인덱스에 위치하는 것이 보장된다.

그래서 그 다음 순회하고 나면 1번째 인덱스부터 순회하기 시작한다.

 

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

1. 0번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 0번째 인덱스와 Swap한다.
2. 1번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 1번째 인덱스와 Swap한다.
...
3. n - 1번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 n번째 인덱스와 Swwap한다.

 

선택정렬은 현재 자료가 정렬되어있던 말건 무조건 전체 리스트를 순회하며 검사하기 때문에 최선의 경우든 한결같이 $O(n^2)$의 시간복잡도를 가지고 있다.

선택정렬의 구현 코드는 아래와 같다.

#include <stdio.h>

int main() {
	int i, j, min, index, temp;
	int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };

	for (i = 0; i < 10; i++) {
		min = 9999;
		for (j = i; j < 10; j++) {
			if (array[j] < min) {
				min = array[j];
				index = j;
			}
		}
		temp = array[i];
		array[i] = min;
		array[index] = temp; // swaping
	}
}

 

💡 삽입 정렬(Insertion Sort)

주어진 자료의 모든 요소를 앞에서부터 차례대로 정렬된 자료 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬이다.

사실 인간이 직접 정렬하는 방식과 제일 흡사한 방식인데, 직접 손안에 있는 카드를 정렬한다고 해보자.

대충 다음과 같은 순서로 행동할 것이다.

 

1. 카드를 하나 고른다.

2. 내가 가지고 있는 카드를 쭉 살펴본다.

3. 현재 카드가 들어가야할 순서에 카드를 껴넣는다.

 

삽입 정렬은 이 순서와 비슷하게 작동한다.

1. 0번 인덱스는 건너뛴다.
2. 0 ~ 1번 인덱스 중 1번 인덱스 값이 들어가야할 위치를 찾아서 넣는다.
3. 0 ~ 2번 인덱스 중 n번 인덱스 값이 들어가야할 위치를 찾아서 넣는다.
...
4. 0 ~ n번 인덱스 중 n번 인덱스 값이 들어가야할 위치를 찾아서 넣는다.

삽입 정렬은 최선의 경우 전체 자료를 한번만 순회하면 되기 때문에(내부의 while문이 수행되지 않음), $O(n)$의 시간복잡도를 가지지만 최악의 경우 $O(n^2)$의 시간복잡도를 가진다.

즉 최선인 경우일수록 삽입 정렬을 쓰면 효율적일 수 있겠다!

#include <vector>

using namespace std;

int main()
{
    vector<int> array = {3, 7, 6, 4, 2, 1};
    int N = array.size();

    // i = 1 부터 시작
    for (int i = 1; i < N; i++)
    {
        int j = i;
        // 자신보다 작은 수가 나올때까지 왼쪽으로 이동하고 옮기기
        while (j > 0 && array[j - 1] > array[j])
        {
            int temp = array[j - 1];
            array[j - 1] = array[j];
            array[j] = temp;
            j--;
        }
    }
}

병합 정렬(Merge Sort)

병합 정렬은 일종의 분할 정복(Divide & Conquer) 중 하나로 큰 문제를 작은 여러 개의 문제로 쪼개서 각각을 해결한 후 결과를 모아서 

병합이라는 이름 그대로 주어진 자료를 잘게 쪼갠 뒤 합치는 과정에서 정렬을 하는 알고리즘이다.

그리고 기존의 위치를 기반으로 divide한 뒤,merge 함으로써 기존의 상대적인 위치가 보존되기 때문에 stable sort이다.

 

같은 방식으로 계속 반복하여 병합하고 있기 때문에 병합 정렬은 보통 재귀 함수로 구현한다.

또한 병합정렬은 항상 $O(nlogn)$의 시간복잡도를 가지기 때문에 효율적이다.

그러나 원소의 개수만큼 리스트를 쪼개고 따로 저장하고 있어야 하기 때문에 $O(n)$의 공간 복잡도를 가진다.

한마디로 메모리를 희생해 수행속도를 향상한 알고리즘이다.

 

#include <iostream>
#define N 10000 // 원하는 원소의 갯수

using namespace std;

int arr[N];
int result[N];

void merges(int left, int right) {
	int mid = (left + right) / 2;
	int i = left;
	int j = mid + 1;
	int k = left;

	while (i <= mid && j <= right) {
		if (arr[i] > arr[j]) {
			result[k++] = arr[j++];
		}
		// 양쪽 리스트에서 최솟값을 비교했는데 오른쪽 리스트가 더 컸을 경우
		// 그대로 왼쪽 리스트의 최솟값이 결과배열에 내려오면 됩니다.
		else {
			result[k++] = arr[i++];
		}
	}

	// 오른쪽 리스트에 아직 결과배열에 들어가지 못한 값이 있으면 그대로 넣어줍니다.
	if (i > mid) {
		while (j <= right) {
			result[k++] = arr[j++];
		}
	}
	else { // 그림의 (6)번 과정
		while (i <= mid) {
			result[k++] = arr[i++];
		}
	}

	// 다시 원래 배열에 옮겨담는 작업
	for (int a = left; a <= right; a++) {
		arr[a] = result[a];
	}
}

void partition(int left, int right) {
	int mid;
	// 두개로 분할하고, 병합하는 과정
	// 병합 함수 merges를 보면 알 수 있듯이, while문 등으로 정렬하면서 병합하게 된다.
	if (left < right) {
		mid = (left + right) / 2;
		partition(left, mid);
		partition(mid + 1, right);
		merges(left, right);
	}
}


int main() {

	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	partition(0, N - 1);

    // 이후 결과 배열인 result를 출력하거나 활용하면 됩니다.

	return 0;
}

퀵 정렬(Quick Sort)

퀵 정렬도 병합정렬과 마찬가지로 분할 정복(Divide & Conquer)을 통한 정렬방법이다.(이러면 차이점이 바로 궁금하다)

병합 정렬과의 차이점은 병합 정렬은 분할 단계에서 아무 것도 안 하고 병합 단계에서 정렬을 수행하나, 퀵 정렬은 분할 단계에서 중요한 작업들을 수행하고 병합 시에는 아무것도 하지 않는다.

 

퀵 정렬의 수행 순서는 다음과 같다.(사실 구현 방식이 조금씩 다른 경우가 있는데, 이게 제일 이해하기 쉽다. 참고)

1. 입력된 자료 리스트에서 하나의 원소를 고른다. 이 원소를 피벗이라고 부른다.(중간값도 괜찮고, 맨 처음이나 끝값도 괜찮다.)
2. 피벗을 기준으로 리스트를 둘로 분할한다.
3. 피벗을 기준으로 피벗보다 작은 원소들은 모두 피벗의 왼쪽으로 옮긴다.
4. 피벗을 기준으로 피벗보다 큰 원소들은 모두 피벗의 오른쪽으로 옮긴다.
# 만약 왼쪽 포인터와 오른쪽 포인터가 엇갈리면 오른쪽 포인터값과 피벗값을 교체한다.(엇갈린 상태에서 왼쪽 포인터는 피벗값보다 큰 값을 가리키고 있다는 점이 전제되어있기 때문에 이를 교환하면 섞인다.)

#include <stdio.h>
 
int data[10] = {4, 1, 2, 3, 9, 7, 8, 6, 10, 5};
 
void quick_sort(int *data, int start, int end){
    if(start >= end){
        // 원소가 1개인 경우
        return; 
    }
    
    int pivot = start;
    int i = pivot + 1; // 왼쪽 출발 지점 
    int j = end; // 오른쪽 출발 지점
    int temp;
    
    while(i <= j){
        // 포인터가 엇갈릴때까지 반복
        while(i <= end && data[i] <= data[pivot]){
            i++;
        }
        while(j > start && data[j] >= data[pivot]){
            j--;
        }
        
        if(i > j){
            // 엇갈림
            temp = data[j];
            data[j] = data[pivot];
            data[pivot] = temp;
        }else{
            // i번째와 j번째를 스왑
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    } 
    
    // 분할 계산
    quick_sort(data, start, j - 1);
    quick_sort(data, j + 1, end);
}

 

참고

https://evan-moon.github.io/2018/10/13/sort-algorithm/

정렬 알고리즘 정리 (Bubble, Selection, Insertion, Merge, Quick)

https://code-lab1.tistory.com/24

[알고리즘] 기본 정렬 알고리즘 비교| stable vs not stable| in-place vs not in-place | 선택 정렬(selection sort)

https://hongku.tistory.com/149

 

자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)

https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

정렬 알고리즘 - 나무위키