정렬이란?

정렬이란?

순서없이 나열된 자료를 특정한 키값에 따라 

오름차순이나 내림차순으로 재 배열하는 것을 의미한다.

정렬은 자료 탐색에 있어 필수적이다.

예를들어 사전에서 단어를 찾을 때 알파벳순으로 정렬되어 있지 않다면 특정한 단어를 찾는 것이 매우 힘들것이다.

물론 컴퓨터로 찾는다면 사람이 찾는것보다는 빨리 찾을 수 있을테지만, 탐색의 효율이 떨어지는것은 피할수 없다.

정렬은 많은 분류가 있지만 수행되는 공간에 따라 내부정렬과 외부정렬로 나뉘어 진다.

내부정렬은 정렬하고자 하는 모든 데이터가 메모리에 올라와 정렬이 수행되는 것을 의미한다.

외부정렬은 정렬하고자 하는 데이터가 너무 크기 때문에 모든 데이터를 메모리에 올려놓을 수 없으므로 일부만 올려놓은 상태에서 정렬한 이것을 다시 합하는 방식이다.

정렬의 종류

※ 내부정렬.

정렬	삽입법	- 삽입 정렬 (Insertion sort).  - 쉡 정렬 (Shell sort).
	교환법	- 선택정렬 (Selection sort).  - 퀵 정렬 (Quick sort)  - 버블 정렬 (Bubble sort).
	선택법	- 힢 정렬 (Heap sort)
	병합법	- 머지 정렬 (Merge sort).
	분포	- 개수정렬 (counting sort).  - 기수 정렬 (radix sort)  - 버킷 정렬 (bucket sort)

※외부정렬

균형적 다방향 머지 정렬.

정렬의 기본 동작

판단 : 두 값의 크기를 비교하여 크고 작음을 판단한다.

교환 : 판단 결과를 만족할 경우 두 값을 교환한다.