정렬

정렬의 종류

내부정렬

- 정렬하고자 하는 파일을 주기억장치에 모두 넣고 정렬하는 방법으로, 정렬 속도가 빠르고 처리하는 데이터양이 적을 경우 적합

삽입법 : 삽입정렬, 쉘정렬

교환법 : 버블정렬, 퀵정렬

선택법 : 선택정렬, 힙정렬

합병법 : 2원 합병정렬

분배법 : 기수정렬

외부정렬

-정렬하려는 파일의 크기가 너무 커서 주기억장치에 모두 적재할 수 없는 경우, 파일을 보조기억장치에 두고 정렬하는 방법으로 속도가 느리다.

디스크를 사용 : k-원 합병정렬

테이프를 사용 : 균형 합병정렬, 다단계 합병정렬, 계단식 합병정렬, 진동 합병정렬

정렬 방법에 따른 분류

비교 정렬

- 각 레코드의 키 값을 두 개씩 비교하여 교환하는 정렬 방법으로 선택 정렬, 삽입 정렬, 쉘 정렬, 퀵 정렬, 버블 정렬, 힙 정렬, 2원 합병 정렬 등이 있다.

분배 정렬

- 레코드의 키 값을 기준으로 전체 레코드 집합을 여러 개의 부분 집합으로 분배하면서 정렬하는 방법으로 기수 정렬이 있다.

내부 정렬 수행시간

Name	Best	Avg	Worst	Run-time  (정수 60,000개)
삽입정렬	n	n^2	n^2	7.438
선택정렬	n^2	n^2	n^2	10.842
버블정렬	n^2	n^2	n^2	22..894
쉘 정령	n	n^1.5	n^2	0.056
퀵 정렬	nlogn	nlogn	n^2	0.014
힙 정렬	nlogn	nlogn	nlogn	0.034
병합 정렬	nlogn	nlogn	nlogn	0.026