정렬 알고리즘

정렬(sorting)은 데이터를 크기 순서대로 늘어놓는 일이다. 정렬해 두면 이진 검색(binary search) 같은 빠른 검색을 쓸 수 있다. 실기 시험은 배열 하나를 주고 특정 정렬의 n회전 뒤 상태를 쓰게 하거나, 정렬 이름과 설명·시간 복잡도(time complexity)를 짝짓게 한다. 이 문서의 회전별 결과는 모두 9, 4, 7, 1, 3을 오름차순으로 정렬한 것이다.

바깥 반복을 한 번 돌 때마다 배열의 일부가 제자리에 확정되는데, 이 바깥 반복 한 번을 회전(pass)이라 한다. 원소가 n개면 아래 세 정렬 모두 n − 1회전으로 끝난다. 예제는 5개이므로 4회전이다.

삽입 정렬

삽입 정렬(insertion sort)은 앞쪽을 이미 정렬된 부분으로 보고, 다음 원소 하나를 그 안의 알맞은 자리에 끼워 넣는 방식이다. 끼울 자리를 찾는 동안 더 큰 원소는 한 칸씩 뒤로 민다.

회전	끼울 값	결과
1	4	4 9 7 1 3
2	7	4 7 9 1 3
3	1	1 4 7 9 3
4	3	1 3 4 7 9

이미 거의 정렬된 데이터라면 밀 원소가 거의 없어 빠르다. 속도는 입력 크기 n이 커질 때 계산 횟수가 느는 정도를 나타내는 빅-O 표기법(big-O notation)으로 잰다. 삽입 정렬의 최선은 O(n), 평균과 최악은 O(n²)다.

선택 정렬

선택 정렬(selection sort)은 아직 정렬되지 않은 부분에서 최솟값을 찾아 맨 앞 원소와 바꾸는 방식이다. 1회전에 첫 자리, 2회전에 둘째 자리가 확정된다.

회전	찾은 최솟값	결과
1	1	1 4 7 9 3
2	3	1 3 7 9 4
3	4	1 3 4 9 7
4	7	1 3 4 7 9

데이터가 이미 정렬돼 있어도 최솟값을 찾으려고 끝까지 비교해야 한다. 그래서 최선·평균·최악 모두 O(n²)다.

버블 정렬

버블 정렬(bubble sort)은 이웃한 두 원소를 비교해 순서가 틀리면 바꾸는 일을 앞에서 뒤로 되풀이한다. 한 회전이 끝나면 가장 큰 값이 거품처럼 맨 뒤로 떠오른다.

회전	결과
1	4 7 1 3 9
2	4 1 3 7 9
3	1 3 4 7 9
4	1 3 4 7 9

평균과 최악은 O(n²)다. 한 회전 동안 교환이 한 번도 없으면 멈추도록 만들면 이미 정렬된 데이터에서 최선 O(n)이 된다.

퀵 정렬과 그 밖의 정렬

퀵 정렬(quick sort)은 기준값인 피벗(pivot)을 하나 고른 뒤, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누고 양쪽을 다시 같은 방식으로 정렬한다. 문제를 작게 쪼개 푸는 분할 정복(divide and conquer) 방식이다. 평균 O(n log n)으로 빠르지만, 피벗이 매번 가장 작거나 큰 값이면 한쪽으로만 쪼개져 최악 O(n²)이 된다. 회전별 결과는 피벗 고르는 방식마다 달라진다.

병합 정렬(merge sort)은 반으로 나눠 각각 정렬한 뒤 합치고, 힙 정렬(heap sort)은 가장 큰 값이 맨 위에 오는 트리 모양 구조인 힙(heap)에서 최댓값을 하나씩 꺼내 뒤에서부터 채운다. 둘 다 최악에도 O(n log n)이다. 힙은 값 하나를 꺼내고 다시 정리하는 데 log n 단계가 들어서, 이를 n번 되풀이하면 n log n이 된다.

시험 포인트

• 정렬된 부분에 끼워 넣기 → 삽입. 최솟값을 찾아 앞과 교환 → 선택. 이웃끼리 비교·교환 → 버블. 피벗으로 분할 → 퀵.
• 선택 정렬 1회전 뒤에는 맨 앞이, 버블 정렬 1회전 뒤에는 맨 뒤가 확정된다.
• 삽입·선택·버블: 평균·최악 O(n²). 퀵: 평균 O(n log n), 최악 O(n²). 병합·힙: O(n log n).