선택·버블·삽입 정렬

선택 정렬(selection sort)·버블 정렬(bubble sort)·삽입 정렬(insertion sort)은 두 값을 견주고 자리를 바꾸는 일을 되풀이해 줄을 차례대로 세우는 기본 정렬입니다. 셋 다 두 겹 반복이라 시간 복잡도(알고리즘과 시간 복잡도)가 O(n²)이지만, 줄을 한 번 훑는 한 회전(pass)이 끝날 때마다 줄의 어느 쪽이 정해지는지가 서로 다릅니다. 시험은 이 차이를 노려 같은 줄을 주고 'n회전 뒤 결과'를 묻습니다. 아래 그림은 같은 줄 5, 4, 3, 8, 1을 세 정렬로 두 회전씩 돌려 결과를 나란히 남깁니다.

1선택 정렬 — 가장 작은 값을 골라 맨 앞으로

선택 정렬은 아직 정해지지 않은 칸 가운데 가장 작은 값을 찾아, 그 구간의 맨 앞 칸과 맞바꿉니다. 1회전에는 1을 찾아 5와 바꿔 1, 4, 3, 8, 5가 되고, 2회전에는 둘째 칸부터 훑어 3과 4를 바꿔 1, 3, 4, 8, 5가 됩니다.

회전마다 앞에서부터 한 칸씩 자리가 정해집니다. 가장 작은 값을 찾느라 남은 칸을 모두 견주므로, 줄이 이미 정렬되어 있어도 견주는 횟수가 줄지 않습니다.

2버블 정렬 — 이웃끼리 바꿔 큰 값을 뒤로

버블 정렬은 이웃한 두 칸을 왼쪽부터 견줘 앞이 크면 맞바꿉니다. 큰 값이 거품처럼 뒤로 떠올라, 1회전이 끝나면 가장 큰 8이 맨 뒤에 섭니다(4, 3, 5, 1, 8). 2회전은 8 앞까지만 견줘 3, 4, 1, 5, 8이 됩니다.

회전마다 뒤에서부터 한 칸씩 자리가 정해집니다. 한 회전 동안 한 번도 바꾸지 않았다면 이미 정렬된 것이라, 거기서 멈추게 짤 수 있습니다.

3삽입 정렬 — 꺼낸 값을 앞쪽 정렬된 줄에 끼운다

삽입 정렬은 둘째 칸부터 값을 하나씩 꺼내, 앞쪽의 정렬된 줄에서 들어갈 자리를 찾아 끼웁니다. 꺼낸 값보다 큰 값은 한 칸씩 뒤로 밉니다. 1회전은 4를 꺼내 5 앞에 넣고(4, 5, 3, 8, 1), 2회전은 3을 꺼내 맨 앞에 넣습니다(3, 4, 5, 8, 1).

앞쪽 세 칸은 정렬되었지만 제자리는 아닙니다. 마지막 1이 들어오면 모두 한 칸씩 밀립니다. 줄이 이미 정렬되어 있으면 꺼낸 값이 바로 자리를 찾아 O(n)에 끝납니다.

세 정렬을 가르는 기준을 한 표에 모았습니다.

예제

실기는 정렬 코드를 주고 출력을 그대로 쓰게 합니다. 다음 C 코드는 어떤 정렬을 몇 회전 돌까요?

#include <stdio.h>
int main(void) {
    int a[5] = {5, 4, 3, 8, 1};
    int i, j, t;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 4; j++)
            if (a[j] > a[j+1]) {
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
    for (i = 0; i < 5; i++)
        printf("%d", a[i]);
    return 0;
}

34158

• 안쪽 반복이 이웃한 a[j]와 a[j+1]을 견줘 앞이 크면 바꾸니 버블 정렬입니다.
• 바깥 반복이 회전 수입니다. i < 2라 두 회전만 돌고, 3, 4, 1, 5, 8이 빈칸 없이 이어 찍힙니다.
• 이 코드는 회전마다 네 번씩 견줍니다. 자리가 정해진 뒤 칸과 견줘도 바꿀 일이 없어 결과는 같습니다.

시험 포인트

• 필기(시험에서는 1과목): 같은 줄을 주고 정렬 이름과 회전 수를 밝혀 결과를 고르게 합니다. 다른 정렬의 결과나 한 회전 덜·더 돈 결과가 오답 보기로 나옵니다 — 선택은 앞이, 버블은 뒤가 한 칸씩 정해지고, 삽입은 앞쪽 정렬된 줄이 한 칸씩 자란다는 것으로 가릅니다. 셋 다 O(n²)이고, 삽입 정렬은 이미 정렬된 줄에서 O(n)입니다.
• 실기: 정렬 코드의 출력을 그대로 씁니다 — 바깥 반복의 횟수(회전 수)와 견주는 부등호(>면 큰 값이 뒤로 가는 오름차순)를 먼저 봅니다. 이름은 한글 이름과 영문으로 씁니다 — 선택 정렬(Selection Sort), 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort).

확인 문제

1. 줄 9, 6, 7, 2, 4를 삽입 정렬로 작은 값부터 정렬합니다. 2회전 뒤 모습을 고르세요.

• ① 2, 4, 7, 9, 6
• ② 6, 2, 4, 7, 9
• ③ 6, 7, 9, 2, 4
• ④ 6, 9, 7, 2, 4

2. (가)~(다)에 맞는 정렬 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 줄 선 학생들 가운데, 아직 자리가 정해지지 않은 학생 중 키가 가장 작은 사람을 찾아 그 구간 맨 앞 학생과 자리를 바꿉니다.
• (나) 옆 사람과 키를 견줘 앞사람이 크면 둘이 자리를 바꾸며 줄 끝까지 갑니다. 한 바퀴를 돌 때마다 가장 큰 학생이 맨 뒤에 섭니다.
• (다) 카드를 한 장씩 받을 때마다, 손에 순서대로 쥔 카드 사이 알맞은 자리를 찾아 끼워 둡니다.

3. 예제 코드의 a[j] > a[j+1]을 a[j] < a[j+1]로 바꾸면 무엇이 찍힐까요? 답을 끝까지 쓴 뒤 정답을 펼치세요.