1. 정렬 이란?
ㅇ 정렬 (Sorting)
- 수많은 자료들을 특정 목적에 맞게 순서있게 재배치하는 것
- 레코드들을 키 값의 순서로 재배치하는 것
. (키 : 자료를 정렬하는데 기준이 되는 값들 ☞ 키(Key) 참조)
ㅇ 정렬 알고리즘 (Sorting Algorithm)
- 컴퓨터에서, 가장 많이 이용되는 연산 중 하나
- 또한, 자료검색의 효율성 제고, 실용성, 이론 설명 등을 위해서도, 정렬 알고리즘이 필요함
- 정렬을 수행하는 다양한 알고리즘들이 있음
. 100개 이상의 정렬 알고리즘들이 개발되어 왔음
ㅇ 정렬 알고리즘의 구성 요소
- 비교 연산 (compare) : 키 값 비교
- 이동 연산 (swap) : 키 값 비교 후, 자료의 위치 바꿈(교환)
2. 정렬 알고리즘의 특징별 분류
ㅇ 정렬 수행시 데이터 저장 위치에 따른 분류
- 내부 정렬 (internal sort)
. 정렬 전 모든 데이터가 주기억장치에 올라와있음
. 따라서, 대용량 데이터에는 적용 어려움
. 例) 교환 정렬, 삽입 정렬, 선택 정렬 등
- 외부 정렬 (external sort)
. 정렬 전 모든 데이터가 외부기억장치에 있고,
. 필요시 일부분씩 만 주기억장치에 올려 정렬
. 속도가 느린 외부 보조기억장치를 사용하므로, 내부 정렬 보다 느림
. 例) 병합 정렬 등
ㅇ 정렬 수행시 저장공간 필요량에 따른 분류
- 제자리 정렬 (in-place sort : in-place 정렬)
. 입력 자료에 할당된 메모리 이외 일정 상수 만큼 작은 추가 메모리 만 필요
. 즉, 입력 크기가 커지더라도 추가 저장공간이 필요치 않음
. 例) 교환 정렬, 삽입 정렬, 선택 정렬, 힙 정렬 등
ㅇ 정렬의 안정함에 따른 분류
- 안정함 (stable sort : 안정 정렬)
. 입력 자료의 순서 그대로 정렬
.. 입력 자료 키 값이 같을 경우에도, 입력되는 순서 그대로 유지됨
. 例) 버블 정렬, 병합 정렬 등
- 안정하지 못함 (nonstable sort)
. 입력 자료의 순서가 바뀔 수 있는 정렬
.. 다중 키 정렬시, 먼저 정렬한 내용이 보존되지 않는 경우
. 例) 선택 정렬, 퀵 정렬 등
ㅇ 재귀적 여부에 따른 분류
- 재귀적 : 퀵 정렬
- 비 재귀적 : 선택 정렬, 삽입 정렬
- 둘 다 사용 : 병합 정렬
ㅇ 정렬의 계산효율성에 따른 분류
- 단순하지만 비효율적 : 버블 정렬, 선택 정렬, 삽입 정렬 등
. 계산효율성이 평균적으로, Θ(n2)
. (실무에서는 거의 구현할 일 없으나, 이론적 비교 검토 필요)
- 복잡하지만 효율적 : 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬 등
. 계산효율성이 평균적으로, Θ(n log n)
ㅇ 실행 방식에 따른 분류
- 비교 기반의 정렬 방식
. 항목 비교하며, `교환`하는 방식 : 버블 정렬, 선택 정렬, 퀵 정렬
. 적절한 위치에, `삽입`하는 방식 : 삽입 정렬, 셸 정렬
. 자료를 먼저 분할하고, `병합`하면서 정렬하는 방식 : 병합 정렬
. (비교 기반 정렬 방식의 특징)
.. 키 값 전체를 비교의 대상으로 삼고 정렬 수행
.. 키 값의 비교 횟수 만을 알고리즘 수행 시간으로 간주
- 키 값의 분포 기반의 정렬 방식
. 기수 정렬, 계수 정렬
3. 정렬 알고리즘의 대표적인 例
ㅇ 버블 정렬 (Bubble Sort)
- 가장 간단한 정렬 알고리즘
- 정렬 방법
. 이웃 요소 간에 대소 비교하고, 필요시 교환을 수행하며,
. 이 과정을 전체 자료에 걸쳐 반복 수행
. 비교를 좌(위)에서 우(아래)로 또는 우(아래)에서 좌(위)로도 진행 가능
- 계산 효율성 : O(n2)
ㅇ 교환 정렬 (Exchange Sort) (때론, 버블 정렬과 동의어로 쓰이기도 함)
- 정렬 방법 : 버블 정렬과 거의 같으나,
. 인접 위치의 두 수 간에 비교/교환이 아니라,
. 두 수의 위치 중 하나를 고정하고 다른 위치를 이동하며 비교/교환을 수행
- 계산 효율성 : O(n2)
ㅇ 선택 정렬 (Selection Sort)
- 정렬 방법
. 가장 큰/가장 작은 자료를 선택하고(찾고),
. 선두로 옮기는(교환하는) 과정을 반복적으로 수행
- 계산 효율성 : O(n2)
- 키 비교 횟수 : 총 n(n-1)/2회로써, `버블 정렬,교환 정렬`과 같음
ㅇ 삽입 정렬 (Insertion Sort)
- 정렬 방법
. 선택한 요소를 정렬된 영역에서 알맞은 위치를 찾아 삽입을 반복적으로 수행
- 특징 : 크기가 작은 정렬 문제에 효율적
- 계산 효율성 : O(n2)
ㅇ 힙 정렬 (Heap Sort)
- 힙 이라는 완전 이진 트리 구조를 통해 정렬하는 방식
ㅇ 퀵 정렬 (Quick Sort)
- 가장 빠른 정렬 알고리즘 중의 하나로 널리 사용됨
- 정렬 방법
. 피봇 값을 선정해, 해당 값을 기준으로 정렬 수행
- 계산 효율성 : O(nlogn)
ㅇ 병합 정렬 (Merging Sort)
- 외부 정렬 방식임
- 정렬 방법
. 자료를 여러 부분 집합으로 분할하고, 각각 정렬한 다음에, 이를 병합하면서 정렬 수행
- 계산 효율성 : O(nlogn)
ㅇ 기수 정렬 (Radix Sort)
- 정렬 방법
. 키 값을 여러 부분 집합으로 분배한 후, 이를 이용하여 정렬 수행
. 데이터의 자리수를 바탕으로 비교해가며, 정렬 수행