알고리듬 - 버블, 선택, 삽입 정렬

버블, 선택, 삽입 정렬은 구현하기 쉬운 대신 성능이 낮은 정렬 알고리즘이다.

이에 대해 하나씩 알아보자.

 

버블 정렬

버블 정렬은 앞부터 인접한 두 개의 수를 비교해 큰 숫자를 뒤로 보내는 작업을 반복한다.

동작은 아래 그림과 같다.

세 번째처럼 교환이 일어나지 않았을 때는 모든 값이 정렬된 것이므로 동작을 멈추게 해 조금이나마 시간을 줄일 수 있다.

 

간단히 코드를 보자면 아래와 같다. 

void bubble_sort(int arr[]) {
    int tmp = 0;
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4-i; j++) {
            if(arr[j] > arr[j+1]) {
                tmp = arr[j]; 
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

시간복잡도는 O(n²)이다. 이 알고리듬은 셋 중에서도 가장 효율이 좋지 않아 거의 사용하지 않는다.

 

선택 정렬

선택 정렬은 정렬 대상에서 크거나 작은 데이터를 찾아 순서대로 배치하는 방식이다.

동작은 아래 그림과 같다.

1. 정렬되지 않은 배열에서 가장 작은(큰) 값을 찾는다.

2. 해당 값을 앞(뒤)부터 순서대로 놓는다.

 

버블 정렬에 비해 동작이 짧아 보이지만

대상을 앞부터 마지막까지 탐색해 최솟값을 찾는 과정을 거치므로 소요 시간은 버블 정렬과 유사하다.

 

코드는 아래와 같다. 

void selection_sort(int arr[]) {
    int minIndex, tmp = 0;
    for(int i = 0; i < 4; i++) {
        minIndex = i;
        for(int j = i+1; j < 5; j++) {
            if(arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }
}

시간복잡도는 O(n²)이다.

 

삽입 정렬

삽입 정렬은 손 안의 카드를 정렬하는 방법과 유사하다.

 * 새 카드가 들어오면 기존 정렬된 카드 사이의 올바른 자리에 삽입하는 형태

 

대상을 선택해 정렬된 영역에서 알맞은 위치에 옮기는(삽입하는) 방식이다.

대상을 옮기면서 정렬된 영역은 한 칸씩 뒤로 민다.

동작은 아래 그림과 같다.

코드는 아래와 같다. 

void insertion_sort(int arr[]) {
    int key, i, j = 0;
    for(i = 1; i < 5; i++) {
        key = arr[i];
        for(j = i-1; j >= 0 && arr[j] > key; j--) {
            arr[j+1] = arr[j];
        }
        arr[j+1] = key;
    }
}

시간복잡도는 O(n²)이다.

 

삽입 정렬의 특징은 다른 두 개의 방법과 달리 정렬이 된 상태면 시간복잡도가 O(n)이라는 것이다.

이 특징을 이용해 고안한 방식으로 쉘 정렬이 있다.