정렬

정렬이란?

정렬(Sorting)은 이름, 학번, 키등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말합니다. 이 알고리즘을 이용해 데이터를 정렬하면 검색을 더 쉽게 할 수 있습니다. 키 값이 작은 데이터를 앞쪽에 놓으면 오름차순(ascending order) 정렬, 그 반대로 놓으면 내림차순(descending order) 정렬이라고 부릅니다.

정렬 알고리즘에는 안정된 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있습니다. 안정된 알고리즘이란 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말합니다. 안정되지 않은 알고리즘은 같은 키 값을 가지는 경우 기존 요소의 순서가 보장되지 않습니다.

종류

위에서도 보았듯이, 정렬은 안정성(stable)을 기준으로 나눌 수 있습니다.

안정된 알고리즘

1. 버블 정렬(Bubble Sort)
2. 단순 삽입 정렬(Straight Insertion Sort)
3. 병합 정렬(Merge Sort)
4. 도수 정렬(Counting Sort)

안정적이지 않은 알고리즘

1. 단순 선택 정렬(Straight Selective Sort)
2. 셸 정렬(Shell Sort)
3. 퀵 정렬(Quick Sort)
4. 힙 정렬(Heap Sort)

정리 순서

안정성을 기준으로 정렬은 위와 같이 나눌 수 있습니다. 하지만 정리하는 순서는 이와 같이 하는 것이 아닌 아래와 같은 순서로 정리할 예정입니다.

1. 버블 정렬
2. 단순 선택 정렬, 단순 삽입 정렬
3. 셸 정렬
4. 퀵 정렬
5. 병합 정렬
6. 힙 정렬
7. 도수 정렬

1번 ~ 3번까지의 정렬은 아주 기본적인 정렬로 나머지 정렬보다 시간적 효율이 떨어지는 알고리즘입니다.

시간 복잡도의 경우 $O(N^2)$로 구해집니다.

4번부터 8번 까지의 정렬의 경우 앞의 3가지 정렬보다 시간적으로 효율적이지만 좀 더 복잡한 형태를 가지고 있는 정렬이므로 앞에 3가지 정렬을 확인한 후 정리하는 것이 좋을 것 같습니다.

정렬 알고리즘 시간 복잡도 비교