[자료구조] 정렬

[자료구조] 정렬

정렬이란 순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차

순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열 하는 것이다. 할일을 순

서대로 정하는 것이나 가게에서 음식을 유통기한 순서대로 냉장고에 진열하는

것, 도서관에서 도서번호 순서대로 책들을 정리하는 것, 이름 순서로 기록되어

있는 전화번호부 등 일상 생활에서 정렬을 사용하고 있다.

자료를 정렬하는데 사용하는 기준이 되는 특정 값을 키라고 한다. 특정 이름이

라던지, 수치 등을 이용할 수 있는데 중복되는 값이 여서는 안된다.

정렬 방법은 실행하는 방법과 정렬이 수행되는 장소에 따라서 분류될 수 있다.


실행 방법에 따른 분류

정렬은 실행하는 방법에 따라 비교식 정렬과 분산식 정렬로 구분할 수가 있다.

비교식 정렬은 비교하고자 하는 각 키값들을 한번에 두개씩 비교하여 교환함으

로써 정렬을 실행하는 방식이다. 그리고 분산식 정렬은 키값을 기준으로 하여

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


정렬 장소에 따른 분류

컴퓨터에서 수행되는 정렬은 컴퓨터 메모리 내부에서 정렬하는 내부정렬과 메

모리의 외부인 보조 기억 장치에서 정렬하는 외부 정렬로 분류할 수 있다.