비교 정렬
1. 버블 정렬: 처음부터 하나씩 1) 비교, 2) 자리 교환 --> 가장 큰 수의 자리가 고정된다.
2. 선택 정렬: 정렬되지 않은 부분에서 최솟값 찾아서, 정렬되지 않은 첫 부분과 switch
3. 삽입 정렬: 정렬된 부분이 있고, 정렬되지 않은 부분의 처음부터 하나씩 1) 비교, 2) 삽입 --> 정렬된 부분의 자리가 점점 채워진다.
4. 쉘 정렬: gap을 이용한 삽입 정렬 --> 빠르게 이동시킨다.
5. 힙 정렬: 1) 루트 노드 <-> 마지막 노드, 2) 루트 노드(가장 큰 것) 자리 확정, 3) 루트로 간 마지막 노드 정리, ...
**정렬 문제의 하한: O(nlogn)
비교정렬이 아닌 정렬
6. 기수 정렬: 숫자를 부분적으로 비교하며 정렬, 안정성(stability)을 가진다.
**외부 정렬: 보조 기억 장치A - 주기억 장치 - 보조 기억 장치B