1. 정렬의 종류
- 내부정렬(Internal Sort)
데이터의 양이 적을 때 주기억장치에서 정렬하는 방식이다. 메모리를 이용하므로 정렬 속도가 빠르지만 정렬할 수 있는 데이터의 양이 RAM의 용량에 따라 제한된다.
- 외부정렬(External Sort)
입력 크기가 주기억장치 공간보다 큰 경우 보조기억장치에 있는 입력(파일)을 나누어 주기억장치에 읽어들인 후 정렬하는 방식으로 2-way 병합 정렬과 n-way 병합 정렬이 있다.
| 구분 | 종류 | 설명 |
| 비교식 | 교환 | Key를 비교하고 교환하여 정렬 - (선택, 버블, 퀵) |
| 삽입 | Key를 비교하고 삽입하여 정렬 - (삽입, 쉘) | |
| 병합 | Key를 비교하고 병합하여 정렬 - (2-way 병합, n-way 병합) | |
| 선택 | 이진 트리를 사용하여 정렬 - (히프, 트리) | |
| 분배식 | 분배 | Key를 구성하는 값을 여러개의 부분집합에 분배하여 정렬 - (기수) |
2. 선택 정렬(Selection Sort)
: 주어진 데이터에서 가장 큰 값 또는 작은 값을 찾아 선택하고 교환하여 정렬
: 구현이 간단하지만 입력 배열의 정렬 여부와 관계 없이 항상 동일한 연상량을 가지고 있어 최적화의 여지가 적음
: 시간복잡도는 O(n^2)
def selectionSort(array):
for i in range(len(array)-1):
minIndex = i
for j in range(i+1, len(array)):
if array[j] < array[minIndex]:
array[minIndex], array[j] = array[j], array[minIndex]▸초기 배열 상태
▸최소값을 찾아 array[i]의 값과 교환
2. 버블 정렬(Bubble Sort)
: 인접한 두 원소를 비교해 자리를 교환하여 정렬
: 구현이 단순하지만 집합 요소의 Swap이 빈번하며 느리다
: O(n^2)
def bubbleSort(array):
for i in range(len(array)-1, 0, -1):
for j in range(i):
if(array[j] > array[j+1]):
array[j], array[j+1] = array[j+1], array[j]
3. 삽입 정렬(Insertion Sort)
: 배열의 인덱스를 확장하여 데이터를 삽입하는 과정을 반복하여 정렬
: O(n^2)
def insertionSort(array):
for i in range(1, len(array)):
for j in range(i, 0, -1):
if(array[j-1] > array[j]):
array[j-1], array[j] = array[j], array[j-1]
4. 쉘 정렬(Shell Sort)
: 일정한 간격으로 데이터의 부분집합을 구성하여 삽입 정렬을 수행
: 입력이 작을때 효율적 → 임베디드에서 주로 사용
: 간격에 따른 그룹별 정렬 방식이 H/W로의 구현에 적합
