Page 198 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

06-1 정렬

이 장에서는 데이터를 일정한 순서로 정렬하는 정렬 알고리즘에 대해 알아보겠습니다.

정렬이란?

정렬(sorting)은 이름, 학번, 키 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순
서로 줄지어 늘어서도록 바꾸는 작업을 말합니다. 이 알고리즘을 이용해 데이터를 정렬하면

검색을 더 쉽게 할 수 있습니다. 만약 사전에 실린 수십만 개의 단어가 알파벳이나 가나다순
으로 정렬되어 있지 않으면 원하는 단어를 찾기가 어려울 것입니다. 그림 6-1처럼 키 값이 작
은 데이터를 앞쪽에 놓으면 오름차순(ascending order) 정렬, 그 반대로 놓으면 내림차순
(descending order) 정렬이라고 부릅니다.

정렬 전 오름차순 정렬 내림차순 정렬

[그림 6-1] 오름차순 정렬과 내림차순 정렬

정렬 알고리즘의 안정성
이 장에서는 여러 가지 정렬 알고리즘 중에서 대표적인 알고리즘 8개를 소개합니다. 이때 정
렬 알고리즘은 안정된(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있습니다. 그림

6-2는 안정된 정렬을 나타낸 것으로, 그림의 왼쪽은 학번 순으로 늘어놓은 시험 점수의 배열
입니다. 막대 높이는 점수를 의미하고 막대 안의 숫자(0~9)는 학번을 의미합니다. 이때 점수
를 기준으로 오름차순 정렬을 하면 그림의 오른쪽처럼 됩니다. 같은 점수일 경우 학번이 작은
사람을 앞쪽에 배치합니다. 안정된 정렬이란 이렇게 같은 값의 키를 가진 요소의 순서가 정렬

전후에도 유지되는 것을 말합니다. 안정되지 않은 알고리즘은 같은 점수인 경우 반드시 학번
순서대로 정렬되지는 않습니다.

198 C 알고리즘