[정렬] 버블 정렬, 선택 정렬, 삽입 정렬

정렬(1)

시간 복잡도가 O(N²)인 정렬 방법을 정리합니다.

• 버블 정렬
• 선택 정렬
• 삽입 정렬

버블 정렬

• 공간 복잡도 : O(1)

가장 큰 원소를 맨 뒤로 보내고 그 다음 원소를 그 앞, ... 을 반복한다.

void Bubble_sort(int ary[], int length) {
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length - 1 - i; j++) {
            if (ary[j] > ary[j + 1])
                swap(ary[j], ary[j + 1]);
        }
    }
}

개선된 버블 정렬 알고리즘이 있다. 두번째 for문에서 모두 정렬된 상태면 더 이상 살피지 않고 끝낸다.

void Bubble_sort_improved(int ary[], int length) {
    bool sorted = false;
    for (int i = 0; i < length; i++) {
        // 정렬된 상태
        if (sorted)
            break;
        sorted = true;
        for (int j = 0; j < length - 1 - i; j++) {
            if (ary[j] > ary[j + 1]) {
                // 정렬되지 않았으니 False 처리.
                sorted = false;
                swap(ary[j], ary[j + 1]);
            }
        }
    }
}

선택 정렬

• 공간 복잡도 : O(1)

가장 작은 원소를 맨 앞으로 보내고, 그 다음 원소를 그 다음으로 보낸다. 가장 작은 원소의 index를 저장해뒀다가 한번 훑은 뒤 swap을 하기 때문에 버블 정렬보다는 빠르게 가능하다.

void Selection_sort(int ary[], int length) {
    int min_index;
    for (int i = 0; i < length - 1; i++) {
        min_index = i;
        for (int j = i + 1; j < length; j++) {
            if (ary[min_index] > ary[j]) {![Image](https://i.imgur.com/jmdyU4f.png)
                min_index = j;
            }
        }
        swap(ary[i], ary[min_index]);
    }
}

삽입 정렬

• 공간 복잡도 : O(1)

두번째 원소부터 시작해서 왼쪽에 있는 원소와 비교한다. 왼쪽의 원소가 기준값보다 더 크면 오른쪽으로 보낸다. 왼쪽의 원소가 더 작거나(올바른 순서로 되어있거나) 배열의 맨 앞까지 오면 멈춘다.
데이터가 이미 어느정도 정리되어 있는 경우 유리하다.
루프 중간에 멈춰도 검사하지 않은 기존 데이터의 순서가 유지되어 안정적이다.

void Insertion_sort(int ary[], int length) {
    int i, j, current;
    for (i = 1; i < length; i++) {
        current = ary[i];
        for (j = i - 1; j >= 0 && ary[j] > current; j--) {
            ary[j + 1] = ary[j];
        }
        ary[j + 1] = current;
    }
}