순서없이 배열되어 있는 자료를 작은 것부터 큰 것까지 오름차순으로 정렬하거나, 큰 것부터 작은 것까지 내림차순으로 재배열하는 것을 정렬이라고 합니다.

분류

정렬이 실행하는 방식과 정렬이 수행되는 장소에 따라서 정렬 방식을 분류할 수 있습니다.

실행 방식

정렬이 실행되는 방식에 따라 비교식 정렬과 분산식 정렬로 구분할 수 있습니다.

비교식 정렬은 비교하고자 하는 키를 한번에 두개씩 비교하여 교환하는 방식으로 실행되며, 분산식 정렬은 키값을 기준으로 여러개의 부분 집합으로 분해하고 각 부분집합을 정렬하는 하는 방식으로 실행됩니다.

정렬 정소

컴퓨터에 수행되는 정렬 장소에 따라서 내부 정렬과 외부 정렬로 분류됩니다.

내부 정렬은 컴퓨터 메모리 내부에서 정렬하고, 외부 정렬은 보조 기억 장치에서 정렬하게 됩니다.

내부정렬은 정렬 속도가 빠르지만, 정렬할 양이 메모리에 따라 제한될 수 있습니다.

• 교환 방식

• 삽입 방식

• 병합 방식

• 분배 방식

• 선택 방식

외부 정렬

보조 기억 장치를 사용하기 때문에 속도는 떨어지지만 내부 정렬로 처리할 수 없는 큰 용량의 자료를 처리할 수 있습니다.

• 병합 방식

외부 정렬에서 병합 방식은 파일로 부분으로 나눈 다음에 각각 내부 정렬 방식으로 처리하여 정렬합니다.