기본적인 정렬 알고리즘 (선택, 삽입, 버블)

정렬 알고리즘 종류와 특징

선택 정렬

선택 정렬은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택한다라고 생각하면 이해하기 쉽습니다.

현재 위의 예시에서는 각 순서마다 정렬되지 않은 범위에서 가장 큰 원소를 찾아 맨 마지막 값의 자리와 변경합니다. 가장 큰값을 찾아 맨 오른쪽 원소와 변경해 오름차순으로 정렬했지만, 매 순서마다 가장 작은 값을 찾아 맨 왼쪽의 원소와 변경해주어도 오름차순 정렬을 구현할 수 있습니다.

순서를 간략히 정리하면 다음과 같습니다
각 루프마다
1.최대 원소를 찾는다.
2.최대 원소와 맨 오른쪽 원소를 교환한다.
3.맨 오른쪽 원소를 제외한다.
하나의 원소만 남을 때까지 위의 루프를 반복

의사 코드는 다음과 같습니다.

selectionSort(A[], n) {
    for last <- downto 2 {
        A[1...last] 중 가장 큰 수 A[k]를 찾는다
        A[K] <-> A[last]; A[k]와 A[last]값을 교환
    }
}

시간 복잡도를 계산한다면
1)for 루프는 n-1번 반복 되고
2)가장 큰 수를 찾기 위한 비교 횟수는 n-1, n-2, … , 2, 1
3)교환은 상수 시간 작업이므로

T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

시간 복잡도는 O(n^2)가 됩니다.

이제 마지막으로 c++ 코드로 작성하면 다음과 같습니다.
(위의 예시에서는 매 순서마다 가장 값이 큰 원소를 가장 오른쪽 원소와 변경함으로써 오름차순 정렬을 구현했지만, 아래의 코드에서는 매 순서마다 가장 값이 작은 원소를 가장 왼쪽의 원소와 변경함으로써 오름차순 정렬을 구현했습니다.)

#include <iostream>

using namespace std;

void print_arr(int a[], int size) {
    for (int i = 0; i < size; i++) {
        cout << a[i] << ' ';
    }
    cout << '\n';
}

void selection_sort(int a[], int size) {
    int min_idx, tmp;

    for (int i = 0; i < size - 1; i++) {
        min_idx = i;
        for (int j = i + 1; j < size; j++) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
        }
        tmp = a[min_idx];
        a[min_idx] = a[i];
        a[i] = tmp;
    }
}

int main() {
    int a[] = { 15, 2, 24, 18, 7, 13, 12, 4, 21, 9 };
    int size = sizeof(a) / sizeof(int);
    print_arr(a, size);
    selection_sort(a, size);
    print_arr(a, size);
    return 0;
}

삽입 정렬

삽입 정렬은 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다고 이해하면 쉽습니다.
(선택 정렬은 위치가 정해져있고 이 위치에 어떤 원소를 넣을지 선택하는 것이었다면, 삽입 정렬은 원소는 정해져있고 이 원소를 어디에 넣을지 선택하는 것이라고 이해하면 될 것 같습니다.)

위의 그림은 삽입 정렬의 전체적인 과정을 보여주는 것이고, 아래 사진은 삽입 정렬의 전체과정 중 한 과정을 상세하게 보여주고 있습니다.

이번에 선택된 원소는 4이고, 이 원소를 어떤 자리에 삽입할지 탐색하는 과정을 보여줍니다.

삽입 정렬의 의사 코드는 다음과 같습니다.

insertionSort(A[], n){
    for i<- 2 to n{
        A[1...i]의 적당한 자리에 A[i]를 삽입한다.
    }
}

시간 복잡도를 계산한다면
1)for 루프는 n-1번 반복 되고
2)최악의 경우 데이터 삽입을 위한 비교는 i-1번 비교

따라서 최악의 경우 T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

시간 복잡도는 O(n^2)가 됩니다.

이제 마지막으로 c++ 코드로 작성하면 다음과 같습니다.

#include <iostream>

using namespace std;

void print_arr(int a[], int size) {
    for (int i = 0; i < size; i++) {
        cout << a[i] << ' ';
    }
    cout << '\n';
}

void insert_sort(int a[], int size) {
    int tmp;

    for (int i = 1; i < size; i++) {
        tmp = a[i];
        int j = i;

        while (j > 0 && a[j - 1] > tmp) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = tmp;
    }
}

int main() {
    int a[] = { 15, 2, 24, 18, 7, 13, 12, 4, 21, 9 };
    int size = sizeof(a) / sizeof(int);
    print_arr(a, size);
    insert_sort(a, size);
    print_arr(a, size);
    return 0;
}

버블 정렬

버블 정렬은 선택 정렬과 기본 개념이 비슷합니다. 버블 정렬에서도 선택 정렬과 같이 이미 해당 순서에 원소를 넣을 위치는 정해져 있고, 어떤 원소를 넣을지 선택한다라고 생각하면 됩니다. 다만 선택 정렬과는 다르게 최대값을 찾고, 그 최대값을 맨 마지막 원소와 교환하는 과정에서 차이가 있습니다.

버블 정렬의 의사 코드는 다음과 같습니다.

bubbleSort(A[], n){
    for last <- downto 2{
        for i <- 1 to last - 1
            if(A[i]>A[i+1]) then A[i] <-> A[i+1] // 교환
    }
}

시간 복잡도를 계산한다면
1)바깥 for 루프는 n-1번 반복 되고
2)안쪽 for 루프는 n-1, n-2, …, 2, 1번 반복
3)원소 교환은 상수시간 작업

따라서 T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)**

시간 복잡도는 O(n^2)가 됩니다.

이제 마지막으로 c++ 코드로 작성하면 다음과 같습니다.

#include <iostream>

using namespace std;

void print_arr(int a[], int size) {
    for (int i = 0; i < size; i++) {
        cout << a[i] << ' ';
    }
    cout << '\n';
}

void buuble_sort(int a[], int size) {
    int tmp;

    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (a[i] > a[j]) {
                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
    }
}

int main() {
    int a[] = { 15, 2, 24, 18, 7, 13, 12, 4, 21, 9 };
    int size = sizeof(a) / sizeof(int);
    print_arr(a, size);
    buuble_sort(a, size);
    print_arr(a, size);
    return 0;
}

출처 : 2015 봄학기 알고리즘 - 부경대 권오흠 교수님