[알고리즘] 정렬의 정의와 분류

정렬의 정의

2개 이상의 자료를 오름차순(ascending)이나 내림차순(descending)으로 재배열하는 것

 

정렬 방법의 분류

1. 실행 방법에 따른 분류

(1) 비교식 정렬 (Comparative Sort)

비교하고자 하는 각 키 값들을 한 번에 두 개씩 비교하여 교환하는 방식

 

(2) 분산식 정렬 (Distribute Sort)

키 값을 기준으로 자료를 여러 개의 부분 집합으로 분해하고, 각 부분집합을 정렬함으로써 전체를 정렬하는 방식.

※ 여기서 키(key)란, 자료를 정렬하는 데 사용하는 기준이 되는 특정 값을 의미.

 

2. 정렬 장소에 따른 분류

(1) 내부 정렬 (Internal Sort)

- 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식

- 정렬 속도가 빠르지만 메모리 용량의 제한을 받음

- 내부 정렬 방식

   1) 교환 방식 : 키를 비교하고 교환하는 방식 (버블 정렬, 선택 정렬, 퀵 정렬 등)

   2) 삽입 방식 : 키를 비교하고 삽입하는 방식 (삽입 정렬, 쉘 정렬 등)

   3) 병합 방식 : 키를 비교하고 병합하는 방식 (2-way 병합과 같은 n-way 병합 정렬)

   4) 분배 방식 : 여러 부분집합에 분배하여 정렬하는 방식 (기수 정렬 등)

   5) 선택 방식 : 이진 트리를 사용하는 방식 (힙 정렬, 트리 정렬 등)

 

(2) 외부 정렬 (External Sort)

- 정렬할 자료를 보조 기억장치에서 정렬하는 방식

- 대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 대용량의 자료의 정렬 가능

- 외부 정렬 방식

   1) 병합 방식 : 파일을 부분 파일로 분리하여 각각을 내부 정렬하고, 병합하는 방식 (2-way 병합 등의 n-way 병합 정렬)