정렬

1. 각 항목간 비교하여 정렬하는 방법

선택, 삽입, 버블 정렬들은 worst O(n^2) 이므로 일반적으로 사용이 쉽지 않다고 생각됩니다.

분할 정복 기법을 추가하여 정렬하는 합병 정렬과 quick 정렬은 O(nlog n) 이지만

quick 정렬은 피벗을 잘 못 선택하면 worst O(n^2)이기 때문에 주의해서 사용해야 하고

합병 정렬은 최소 정렬할 자료의 크기 만큼 저장소가 추가로 필요하고 recursive로 구현할 때 stack 넘침의 위험성이 있습니다.

그래서 가장 용이하게 시도할 수 있는 방법으로 우선 순위 queue를 구현하는 방법인 heap 정렬을 생각해 볼 수 있을 것 같습니다.

2. 정렬될 결과에서 배치될 순서를 기준으로 정렬하는 방법

각 항목을 서로 비교하여 정렬하는 방법들은 O(nlog n)가 최선이지만 집합에 각 항목이 몇 개씩 있는지 세는 방법으로 정렬하는 counting sort는 O(n)까지 빨라질 수 있습니다. 이 방법을 확장하여 기수 단위로 counting 정렬하는 방법이 radix sort 입니다. radix sort가 사용이 가능하다면 정렬에서는 radix sort를 우선적으로 사용하는 것이 좋을 것 같습니다.