정렬이란?

정렬의 개념

정렬 Sort 란! 순서대로 배열하는 것이다.

기준값 Key : 정렬하는 데 사용하는 기준이 되는 특정 값

 

정렬 방식의 분류

<내부정렬>

 

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

속도는 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리 용량에 따라 제한된다.

구분	종류	설명	예시
비교식	교환방식	키를 비교하고 교환하여 정렬	선택 정렬, 버블 정렬, 퀵 정렬
	삽입방식	키를 비교하고 삽입하여 정렬	삽입 정렬, 셸 정렬
	병합 방식	키를 비교하여 병합하여 정렬	2-way 병합, n-way 병합
	선택 방식	이진 트리를 사용하여 정렬	히프 정렬, 트리 정렬
분배식	분배 방식	키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬	기수 정렬

 

<외부정렬>

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