Sort - Intro

• 실행 방법에 따른 분류
  • 비교식 정렬: 두 값을 비교하여 정렬하는 방식
  • 분산식 정렬: 하나의 키 값을 잡아서 부분집합으로 나누어서 정렬함으로써 전체를 정렬하는 방식
• 정렬 장소에 따른 분류
  • 내부 정렬
    • 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식. 용량이 제한적이다
    • 교환 방식 (Selection, Bubble, Quick), 삽입 방식 (Insertion, Shell), 병합 방식 (2-way, n-way), 분배 방식 (radix), 선택 방식 (heap, tree) 등이 있다
  • 외부 정렬
    • 정렬할 자료를 보조 기억장치에서 정렬하는 방식. 속도가 떨어지지만 대용량이 가능하다
    • 병합 방식 (2-way, n-way) 이 있다
• Big O
  • O(n²): Bubble, Selection, Insertion, Shell, Quick
  • O(n log n): Heap, Merge

O(kn): radix