[Computer Algorithms] Basic Sorting Algorithms : Bubble Sort, Selection Sort, and Insertion Sort (거품 정렬, 선택 정렬, 삽입 정렬)

1. Bubble Sort (거품 정렬)

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 매 회전마다 회전 구간에서의 최댓값이 최우측으로 간다.

void bubbleSort()
{
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = 1; j < v.size() - i; j++)
        {
            if (v[j - 1] > v[j])
            {
                int temp = v[j - 1];
                v[j - 1] = v[j];
                v[j] = temp;
            }
        }
    }
}

Best case : O(N^2) (이미 정렬 되어 있어도 버블이 이동하며 대소 비교는 계속 함)

Average Case : O(N^2)

Worst case : O(N^2)

 

- 장점

1. 구현이 매우 간단하고, 소스코드가 직관적이다.

2. In-place Sorting이다. (알고리즘 수행 동안 다른 메모리 공간을 필요로 하지 않는다.)

3. Stable sorting이다. (동일한 값이어도 정렬 후 순서가 유지된다.)

- 단점

1. 시간 복잡도가 비효율적이다.

2. 정렬 되어있지 않을 수록, 교환 연산이 많이 얼아난다.

 

2. Selection Sort (선택 정렬)

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘. 매 회전마다 최솟값을 찾고, 최좌측 값과 바꾼다.

void selectionSort()
{
    for (int i = 0; i < v.size() - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < v.size(); j++)
        {
            if (v[j] < v[minIndex])
            {
                minIndex = j;
            }
        }
        int temp = v[minIndex];
        v[minIndex] = v[i];
        v[i] = temp;
    }
}

Best case : O(N^2) (이미 정렬 되어 있어도 최솟값을 찾는 루프만 해도 O(N))

Average Case : O(N^2)

Worst case : O(N^2)

 

- 장점

1. 구현이 매우 간단하고, 소스코드가 직관적이다.

2. In-place Sorting이다.

3. 비교 횟수는 많지만 실제 교환 횟수는 적기 때문에, 많은 교환을 필요로 하는 자료 상태에서는 비효율적이다.

- 단점

1. 시간복잡도가 비효율적이다.

2. Unstable Sorting이다.

 

3. Insertion Sort (삽입 정렬)

2번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘. 매 회전 마다 기준값보다 큰 값들은 뒤로 보내고 기준값보다 작은 값 바로 뒤에 삽입한다.

void insertionSort()
{
    for (int i = 1; i < v.size(); i++)
    {
        int temp = v[i];
        int prevIndex = i - 1;
        while (prevIndex >= 0 && temp < v[prevIndex])
        {
            v[prevIndex + 1] = v[prevIndex];
            --prevIndex;
        }
        v[prevIndex + 1] = temp;
    }
}

Best case : O(N) (이미 정렬되어 있는 경우)

Average Case : O(N^2)

Worst case : O(N^2)

 

- 장점

1. 구현이 매우 간단하고, 소스코드가 직관적이다.

2. In-place Sorting이다.

3. Stable Sorting이다.

4. 대부분의 원소가 이미 정렬되어 있을 때, 매우 효율적이다.

5. Selection Sort나 Bubble Sort에 비해 상대적으로 빠르다.

- 단점

1. 최악의 경우 오래걸린다.

2. 배열의 길이가 길어질수록 비효율적이다.