[정렬] 거품 정렬, 선택 정렬, 삽입 정렬

거품 정렬, 선택 정렬, 삽입 정렬이 무엇인지, 시간 복잡도를 계산하고 소스코드를 구현해본다.

또한, 각 정렬의 특징을 알아보고 마지막으로 각 정렬을 비교해 무엇이 더 효율적인지에 대해 알아본다.

 

1. 거품 정렬(Bubble Sort)

 

1) 거품 정렬이란

서로 인접한 두 원소를 비교해, 대소 관계에 따라 자리를 바꿔주는 정렬이다.

1회전에 첫 번째 원소를 두번 째 원소와, 두 번째 원소를 세 번째 원소와 ,,, N-1을 N번째 원소와 비교해 교환해준다.

다음과 같은 과정을 수행하고 나면, N번째 자리에 가장 큰(혹은 가장 작은) 원소가 위치하게 된다.

이를 N-1번 수행하고 나면 거품이 일어나듯 정렬이 완료된다.

 

다음은 이해를 돕기 위한 유튜브 영상이다.

 

 

2) 거품정렬의 비교 횟수 시간 복잡도

거품 정렬은 어떠한 경우에도 같은 비교 횟수를 수행하게 된다.

(N-1) + (N-2) +... + 2 + 1 = n(n-1)/2

따라서, T(N) = O(n^2) 이다.

 

3) 거품 정렬의 특징

언제나 O(n^2)이기 때문에, 시간 복잡도 측면에서 매우 비효율적이다.

별도의 메모리 공간이 필요하지 않은 in-place sort이다.

중복 원소가 있을 때, 중복되는 각 원소의 위치가 지켜지는 stable sort이다.

 

4) 거품 정렬 소스코드 (Java, 비 내림차순)

public static void bubbleSort(int[] arr){
    int N = arr.length;
    for (int i = 0; i < N-1; i++){
        for (int j = 0; j < N-i-1; j++){
            if (arr[j] > arr[min]){
                int tmp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

여러 블로그에는 첫 번째 루프 문에 오류가 있는 곳이 많다.

for(int i = 0; i < arr.length; i++)가

for(int i = 0; i < arr.length - 1; i++) 혹은 for(int i = 1; i < arr.length; i++)이 되어야 한다.

 

2. 선택 정렬 (Selection Sort)

 

1) 선택 정렬이란?

각 위치에 들어가야 할 원소를 배열에서 찾아 선택해 넣는 정렬이다.

1회전에 첫 번째 위치와 각 위치의 원소를 비교해 가장 작은 (혹은 가장 큰) 원소와 자리를 교환한다.

그렇게 되면 가장 작은 값(혹은 가장 큰 값)이 첫 번째 위치에 위치하게 된다.

2회전에는 두 번째 위치부터 위 과정을 수행한다.

이를 N-1번 실행하게 되면 전체 배열이 정렬된다.

 

다음은 이해를 돕기 위한 유튜브 영상이다.

 

2) 선택 정렬의 비교 횟수 시간 복잡도

선택 정렬 또한 어느 경우에도 같은 비교 횟수를 가진다.

(N-1) + (N-2) +... + 1 = n(n-1)/2

따라서, T(N) = O(n^2)이다.

 

3) 선택 정렬의 특징

언제나 O(n^2)이기 때문에, 시간 복잡도 측면에서 매우 비효율적이다.

하지만, 실제 교환하는 횟수는 계속 교환해주어야 하는 버블 정렬에 비해 적다.

별도의 메모리 공간이 필요하지 않은 in-place sort이다.

중복 원소가 있을 때, 중복되는 각 원소의 위치가 지켜지지 않는 unstable sort이다.

 

4) 선택 정렬 소스코드 (Java, 비 내림차순)

public static void selectionSort(int[] arr){
    int N = arr.length;
    for (int i = 0; i < N-1; i++){
        int min = i;
        for (int j = i+1; j < N; j++){
            if (arr[j] < arr[i]) min = j;
        }
        int tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
    }
}

 

3. 삽입 정렬 (Insertion Sort)

 

1) 삽입 정렬이란?

삽입 정렬은 좌측의 정렬돼있는 부분 배열에 오른쪽 원소들을 하나씩 삽입해 전체 배열을 정렬시킨다.

1회전에는 첫 번째 원소가 정렬돼있는 부분 배열이다.

두 번째 원소를 첫 번째 원소와 비교해 삽입해 정렬시킨다.

2회전에는 1~2 위치의 부분 배열이 정렬돼있는 부분 배열이다.

세 번째 원소를 부분 배열과 비교해 정렬 조건에 맞는 위치를 찾아 정렬시킨다.

N번째 원소까지 삽입하면 전체 배열이 정렬된다.

 

2) 삽입 정렬 비교 횟수 시간 복잡도

거꾸로 정렬되어 있어 각 회전마다 모든 비교가 이루어지는 것이 worst-case이다.

때문에, 1 + 2 +... + (N-1)의 비교가 이루어질 것이고 n(n-1)/2이 된다.

하지만, 모두 정렬돼있어 첫 비교만에 모든 회전이 끝나는 best-case의 경우,

총 N-1번의 비교가 이루어진다.

 

W(n) = O(n^2), B(n) = O(n)

 

3) 선택 정렬의 특징

worst case의 경우, 버블 정렬과 삽입 정렬과 동일한 n(n-1)/2의 비교 횟수이지만

확률 값을 계산해 average-case를 계산해보면 n(n-1)/4가 되어 선택 정렬을 사용하는 것이 버블 정렬, 삽입 정렬에 비해 합리적이다.

또한, 배열이 이미 정렬돼있을 가능성이 높다면 O(n)의 매우 효율적인 알고리즘이 된다.

stable sort, in-place sort이다.

 

4) 선택 정렬 소스코드 (Java, 비 내림차순)

public static void insertionSort(int[] arr){
    int N = arr.length;
    for (int i = 1; i < N; i++){
        int val = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > val){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = val;
    }
}

 

- 거품 정렬, 선택 정렬, 삽입 정렬의 비교

알고리즘	비교 횟수	교환 횟수	추가 메모리
버블정렬	T(n) = (n^2)/2	W(n) = 3(n^2)/2	제자리 정렬
		A(n) = 3(n^2)/4
삽입정렬	W(n) = (n^2)/2	W(n) = (n^2)/2	제자리 정렬
	A(n) = (n^2)/4	A(n) = (n^2)/4
선택정렬	T(n) = (n^2)/2	T(n) = 3n	제자리 정렬

*각 값은 근사치이다.

 

각 교환 비용(원소를 교환해서 레코드를 저장하는 비용)이 비싸다면 선택 정렬을 사용하는 것이 효율적이다.

각 비교 비용이 비싸다면 삽입 정렬을 사용하는 것이 효율적이다.

 

참조)

Richard E. Neapolitan. (2014). Foundations of Algorithms (5/E)