정렬(sort)

<정렬(sort)>

​2개 이상의 자료를 작은 것부터 큰 것 순서의 오름차순(ascending)이나 큰 것부터 작은 것 순서의 내림차순(descending)으로 재배열하는 것
키 - 자료를 정렬하는데 사용하는 기준이 되는 특정 값 

 

[정렬의 예]

<실행 방법에 따른 분류> 

1. 비교식 정렬(comparative sort)
비교하고자 하는 각 키 값들을 한번에 두 개씩 비교하여 교환하는 방식으로 정렬을 실행하는 방법
2. 분산식 정렬(distribute sort)
키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법

 

<내부 정렬(internal sort)>

​정렬할 자료를 메인 메모리에 올려서 정렬하는 방식
정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한됨 

 

[내부 정렬 방식]
- 교환 방식 : 키를 비교하고 교환하여 정렬하는 방식 (선택 정렬, 버블 정렬, 퀵 정렬)
- 삽입 방식 : 키를 비교하고 삽입하여 정렬하는 방식(삽입 정렬, 쉘 정렬)
- 병합 방식 : 키를 비교하고 병합하여 정렬하는 방식 (2-way병합, n-way병합)
- 분배 방식 : 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식 (기수 정렬)
- 선택 방식 : 이진 트리를 사용하여 정렬하는 방식 (히프 정렬, 트리 정렬) 

 

<외부 정렬(external sort)>

​정렬할 자료를 보조 기억장치에서 정렬하는 방식
대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬 가능 

 

[외부 정렬 방식]

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

Copyrightⓒ2014 By 한빛아카데미(주)