[기초] 버블 정렬, 선택 정렬, 삽입 정렬에 대하여

정렬 알고리즘

정렬 알고리즘이란 원소들을 일정한 순서대로 열거하는 알고리즘이다.

정렬 알고리즘은 다양한 알고리즘들이 있다. 이번 포스팅에 들어갈 버블 정렬, 선택 정렬, 삽입 정렬 이외에도 합병 정렬, 퀵 정렬, 힙 정렬 들이 있지만 기본적으로 버블/선택/삽입을 제외한 알고리즘은 어려운 편에 속하므로 먼저 세 가지 알고리즘에 대해 공부하자.

 

버블 정렬 (Bubble Sort)

버블 정렬은 정렬하는 모습이 거품이 꺼지는 모습과 비슷하기 때문에 붙여진 이름이라고 한다. 아마 가장 처음 배우는 정렬 알고리즘이 될 것이고, 별로 좋은 알고리즘이 아니기에 실전에서는 잘 사용되지 않는다. 하지만 이해하기는 제일 쉽다.

 

간단히 말하면, 현재 배열 요소와 그 다음 배열 요소를 비교해 왼쪽이 오른쪽보다 크면 교환한다. 그림으로 보자.

 

위 그림에서 3과 5를 비교했을 때, 3이 5보다 작으므로 둘은 교환하지 않는다.

 

다음으로 넘어가 5와 4를 비교했을 때, 5가 4보다 크므로 둘이 교환한다.

 

또다시 다음으로 넘어가 5가 2보다 크므로 둘이 교환한다.

 

5가 1보다 크므로 둘이 교환한다.

 

첫 번째 과정을 끝마쳤을 때, 배열에서 가장 큰 수였던 5가 가장 뒤로 이동되었다. 이후에는 이 과정을 반복해주면 된다.

배열의 크기가 N이라 했을 때, N - 1개의 아이템과 비교해야 한다. 헌데 최악의 경우에는 모든 아이템을 교환해야 하므로 버블 정렬의 시간 복잡도는 O(n^2)이다.

 

버블 정렬을 코드로 구현하면 다음과 같다.

 

C++

void BubbleSort(int arr[], int size) {
    for (int i = 0; i < size; ++i)
        for (int j = 0; j < size - i - 1; ++j)
            if (arr[j] > arr[j + 1]) 
                swap(arr[j], arr[j + 1]);
}

Python

def BubbleSort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j] # Swap의 간편화

 

선택 정렬 (Selection Sort)

선택 정렬은 가장 작은 아이템의 위치를 다른 변수에 저장해둔 후 첫 번째 자리에 다른 변수에 있던 값을 넣는다. 다음 과정에서는 두 번째 자리에 다음으로 작은 값을 넣고, 배열을 전부 돌 때까지 반복한다. 그림으로 보자.

 

처음에 3이 있는 자리를 i라고 놨을 때, j는 i 다음 인덱스부터 가장 작은 수의 인덱스를 탐색한다. 이를 minidx라고 하자.

위 그림에서는 1이 가장 작으므로 minidx는 4이므로, 배열 인덱스 0과 인덱스 4의 자리를 바꾼다.

 

1과 3의 자리가 바뀌었다. 첫 번째 과정을 마쳤으므로, 이번에는 2가 가장 작은 수이므로 배열 인덱스 1과 3의 자리를 바꾼다.

 

해당 과정을 끝까지 반복해주면 자연스레 오름차순으로 정렬이 된다.

 

선택 정렬은 버블 정렬과는 다르게 N번의 교환을 하지 않는다. minidx를 저장해 놓아 매 과정마다 한 번만 교환하므로 선택 정렬이 버블 정렬보다 더 나은 알고리즘이라고 할 수 있다.

 

C++

void SelectionSort(int arr[], int size) {
    int minidx;

    for (int i = 0; i < size - 1; ++i) {
        minidx = i;
        
        for (int j = i + 1; j < size; ++j)
            if (arr[j] < arr[minidx]) 
                minidx = j;
        
        swap(arr[i], arr[minidx]);
    }
}

Python

def SelectionSort(arr):
    for i in range(len(arr) - 1):
        minidx = i

        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minidx]:
                minidx = j

    arr[i], arr[minidx] = arr[minidx], arr[i] # Swap의 간편화

 

삽입 정렬 (Insertion Sort)

삽입 정렬은 정렬 범위를 1칸씩 확장하며 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교해 알맞은 자리에 삽입한다. 즉, 가면 갈수록 왼쪽은 이미 정렬된 부분이고 오른쪽은 정렬되지 않은 부분이므로 정렬할 부분의 원소를 이미 정렬된 부분에 하나씩 삽입하는 것이다. 그림으로 보자.

 

삽입 정렬은 인덱스 1번부터 시작한다. 즉, 값 5부터 시작한다. 3과 5는 이미 정렬되어 있으므로 건드리지 않는다. 다음 과정에서 4는 5보다 작으므로 서로 교환한다. 또한 3은 4보다 작으므로 다음 사이클로 넘어간다.

 

2는 5보다 작으므로 교환하고, 2는 4보다 작으므로 교환하고, 2는 3보다 작으므로 교환한다. 해당 과정을 끝까지 마치면 1도 맨 앞으로 이동되며 자연스레 오름차순 정렬이 될 것이다.

 

잘 보면 전체적인 범위는 정방향으로 늘어나지만, 정렬하는 과정 자체는 역방향인것을 알 수 있다. 또한 삽입 정렬은 필요한 요소만 스캔하지만 선택 정렬은 모든 요소를 스캔하므로 통상적으로는 삽입 정렬이 선택 정렬보다 빠르다.

 

C++

void SelectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; ++i)
        for (int j = i + 1; j > 0; --j) {
            if (arr[j - 1] > arr[j])
                swap(arr[j - 1], arr[j]);
            else
                break;
        }
}

Python

def InsertionSort(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1): # 안쪽은 역방향
            if arr[j - 1] > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1] # Swap의 간편화

 

총정리

정렬의 가장 기초적인 알고리즘들이다. 아마 실전에서는 내장 함수를 쓰겠지만, 원리 정도는 알아둬야 한다고 생각한다.

 

간단히 정리해본다면

• 버블 정렬 : 인접한 원소끼리 비교/교환
• 선택 정렬 : 최솟값을 찾아 맨 앞으로 이동
• 삽입 정렬 : 이미 정렬된 부분(왼쪽)과 정렬되지 않은 부분(오른쪽)을 비교/교환
  가장 빠르지만 배열이 길어질수록 효율이 떨어진다고 알려져 있음

이며, 삽입 정렬만 최적의 경우 O(n)의 시간복잡도를 가지고 나머지 경우는 모두 O(n^2)의 시간복잡도를 가진다.

앞서 설명한 모든 정렬들은 내림차순 정렬로도 활용할 수 있으며, i와 j 변수를 조금씩 변형하면 된다. 직접 해보면 좋은 경험이 될 것이다.