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

13 13
12 12
11 11
10 10 10 10
9 9
8 8
6 6 정렬 6 6
4 4
0 1 2 3 4 5 6 7 8 9 학번 3 2 4 9 1 6 8 7 5 0

같은 키 값인 요소의 순서가 정렬 전후에도 유지됩니다.
[그림 6-2] 안정된 정렬

내부 정렬과 외부 정렬
30장의 카드를 한 줄로 늘어놓을 수 있는 책상에서 트럼프 카드를 정렬한다고 가정해 보겠습

니다. 만약 카드가 30장 이하라면 모든 카드를 책상에 늘어놓고 한 번에 훑어보면서 작업할
수 있지만 카드가 500장이라면 책상에 모든 카드를 늘어놓을 수 없기 때문에 큰 책상을 따로
마련해야 합니다. 정렬 알고리즘도 하나의 배열에서 작업할 수 있는 경우에는 내부 정렬

(internal sorting)을 사용하고, 하나의 배열에서 작업할 수 없는 경우에는 외부 정렬(external
sorting)을 사용합니다.

1. 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘입니다.
2. 외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘입니다.

외부 정렬은 내부 정렬을 응용한 것으로, 외부 정렬을 구현하려면 작업을 위한 파일 등이 필
요하고 알고리즘도 복잡합니다. 이 책에서 다루는 알고리즘은 모두 내부 정렬입니다.

정렬 알고리즘의 핵심 요소
정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입이며 대부분의 정렬 알고리즘은 이 세 가지 요
소를 응용한 것입니다.

06•정렬 199