[20210916] 정렬 알고리즘

정렬을 위한 알고리즘을 정리하려고 한다.

 

1. 선택 정렬: 큰(작은) 키 값을 찾아 교환한다.

 

2. 버블 정렬: 인접한 키 값을 교환하고, 이미 정렬돼있으면 중단한다.

 

3. 삽입 정렬: 자신의 위치를 찾아서 삽입한다.

 

4. 쉘 정렬: 좀 더 개선된 삽입 정렬이다.

 

5. 퀵 정렬: 자료의 중갑 값을 정한 후 정렬한다.

 

6. 힙 정렬: 이진 트리 구조를 만들어 정렬한다.

 

7. 이진 병합 정렬: 두 개의 키를 한 쌍으로 정한 후 정렬한다.

 

8. 버킷 정렬: 기수 값에 따라 분배하여 정렬한다.

 

 

시간 복잡도(Big-O 표기법 사용) 비교 - 최선 ~ 최악을 같이 표기함

삽입 정렬 - O(n ~ n^2)

버블 정렬, 선택 정렬 - O(n^2)

쉘 정렬 - O(n ~ n^1.5)

퀵 정렬 - O(nlog₂n ~ n^2)

힙 정렬, 이진 병합 정렬 - O(nlog₂n)

버킷 정렬 - O(dn) (d는 자릿수)