삽입, 선택, 버블 정렬

삽입, 선택, 버블 정렬

http://sweeper.egloos.com/918244

정렬 파트 정리에 앞서 삽입, 선택, 버블 정렬에 대해 먼저 정리하려 한다. 

아래 세 가지 정렬은 기본적으로 정렬의 개념을 알기 위한 것이지 실제로 쓰이기에는 효율이 너무 안 좋다. 하지만 정렬되어야 할 요소의 수가 적다면, 구현의 간편함으로 인한 메리트가 있다고 생각한다. 가장 간단한 버블 소트 같은 경우는 실제 코딩시에도 (요소의 수가 적은 경우에 한해) 너무 간편해서 가끔 쓰일 때가 있다.

1. 삽입 정렬 (insertion sort)

배열의 처음 요소 2개를 data[0]과 data[1]을 비교해 정렬되어 있지 않으면 교환한다. 그 다음 data[2]가 고려되며 적절한 위치에 삽입된다. data[2]가 data[0]보다 작다면 data[2]가 0번째 위치에 들어가고 data[0]과 data[1]은 뒤로 밀릴 것이다. (data[2]-data[0]-data[1]) 자료의 각 요소 data[i]가 적절한 위치 j (0 <= j <= i)에 삽입되며 data[i]보다 큰 요소는 한 칸씩 뒤로 밀린다.

두 번째 위치부터 시작하며, 정렬 패턴을 간단하게 표시하면 아래와 같다.

public static void selectionSort(int[] a){

for(int i=1;i<a.length;i++){

int temp = a[i];

for(int j=i;j>0 && temp < a[j-1];j--){

swap(a,j,j-1);

}

}

}

최적의 경우는 물론 모든 데이터가 미리 정렬이 되어 있는 경우일 것이다. 이 때는 당연히 O(n)의 복잡도를 지닐 것이며 최악의 경우는 역순으로 정렬된 경우인데 이 때는 O(n^2)의 복잡도를 지닌다. 하지만 삽입 정렬 알고리즘의 평균 비교 및 이동 횟수는 최악의 경우인 O(n^2)과 같다. 

하지만 삽입 정렬 내부 반복문은 생각보다 빨라 데이터의 수가 8~20 개 근처일 때 가장 빠른 알고리즘이 될 수도 있다. 그리고 삽입 정렬은 마지막에 정리할 버블 정렬과 흡사하다.

2. 선택 정렬 (selection sort)

선택 정렬은 아래와 같이 동작한다.

1. 배열의 가장 작은 값을 찾는다.
2. 첫 번째 위치의 값과 교환한다.
3. 1, 2번 작업을 반복한다. 
(반복시 2.의 위치 증가-> 1회 첫 번째 위치와, 2회 두 번째, n회 n 번째 위치와 교환)
(반복시 이미 찾아진 작은 값은 찾기 작업에서 제외)

예)
1. 31 25 12 22 11 -> 가장 작은 값 : 11, 교환 위치 첫번째 -> (31과 11 교환)
2. 11 25 12 22 31 -> 가장 작은 값 : 12, 교환 위치 두번째 -> (25와 12 교환)
3. 11 12 25 22 31 -> 가장 작은 값 : 22, 교환 위치 세번째 -> (25와 22 교환)
4. 11 12 22 25 31 -> 가장 작은 값 : 25, 교환 위치 네번째 -> 같으므로 교환 X

위에서 보듯이 선택 정렬의 목적은 교환의 국부화이다.

void SelectionSort(int arr[], int MAX) {
    int i, j;
    int min, temp;
    for(i=0; i<MAX-1; i++) {
        min = i;
        for(j=i+1; j<MAX; j++) {
            if(arr[j] < arr[min]) min = j;
        }
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

출처: http://luckyyowu.tistory.com/127 [요우의 내맘대로 블로그]

일반적인 경우에 삽입 정렬보다 뛰어나나 선택 정렬 또한 어떠한 경우에도 복잡도는 O(n^2)이다. 한 번의 과정에서 최소값과 최대값을 동시에 뽑아내는 칵테일 정렬 (cocktail sort)도 있다고 한다.


3. 버블 정렬 (bubble sort)

가장 간단하고 쉬운 정렬 방법이며 exchange sort 라고도 불린다. 배열의 아래에서 위로 올라가며 값을 반복적으로 비교해 적은 값을 앞에 위치시킨다. 즉 data[n]과 data[n-1]을 비교하고 교환하고, data[n-1]과 data[n-2]를 비교하고 교환하는 식의 연속이다. (방향은 아래->위이든, 위->아래이든 상관없다)

정렬 패턴을 정리하면 다음과 같다.

for (i = 0; i < n - 1; i++) 
{
    for (j = 0; j < n - 1 - i; j++)
    {
        // 두 이웃 비교 
        if (a[j+1] < a[j])    
        {  
            // 교환 a[j], a[j+1]
            tmp = a[j];       
            a[j] = a[j+1];
            a[j+1] = tmp;
        }
    }
}

버블 정렬 역시 복잡도는 O(n^2)이라 실제로 쓰기에는 비효율적이라 할 수 있다.


4. 비교

앞에서 살펴본 바와 같이 삽입, 선택, 버블 정렬은 모두 복잡도 O(n^2)으로 실제 사용하기에 비효율적인 정렬 알고리즘들이다. (개체수가 적다면 쓸만하지만...) 하지만 셋 중에서 굳이 비교하자면 가장 간단하게 구현할 수 있는 버블 정렬의 효율이 제일 떨어진다.

버블 정렬은 최악의 경우에는 삽입 정렬과 동등하지만 평균적으로 두 알고리즘의 정렬시 값 교환 회수는 상당한 차이를 보인다. 실험에 의하면 랜덤 리스트에서 삽입 정렬이 버블 정렬보다 상당히 뛰어난 성능을 보였다고 한다. 이러한 이유들로 최근의 알고리즘 책들은 버블 정렬 보다 삽입 정렬 설명을 선호하는 편이다.

게다가 버블 정렬은 최근에 나온 CPU에서 상당히 낮은 성능을 보인다. Astrachan의 스트링 정렬 (with JAVA) 실험을 보면 버블 정렬은 최근의 CPU에서 삽입 정렬보다 대략 5배, 선택 정렬보다는 40% 정도 느렸다고 한다.

결국 같은 O(n^2) 복잡도를 지니는 세 개의 정렬 알고리즘 중에서는 삽입 정렬이 가장 효율적이라고 할 수 있다. 하지만 효율적인 정렬 알고리즘의 복잡도는 O(n^2)이 아니라 (현재까지는) O(n(log n))를 지향해야 된다. 효율적인 정렬 알고리즘에 대해서는 다음에 정리하자.