컴퓨터알고리즘#10
LeeMir, 14 April 2021
정렬 일반
비교정렬의 하한
- 비교정렬
- 비교에 기초한 정렬
- 개체 쌍을 비교함으로써 정렬
- 예 : 버블 / 선택 / 삽입 / 힙 / 합병 / 퀵
- 어떤 비교정렬 알고리즘도 최소 log(n!) 시간을 소요
log(n!) >= log(n/2)^(n/2) = (n/2) log (n/2)- 그러므로 어떤 비교정렬 알고리즘이라도 Ω(n log n) 시간에 수행
정렬의 안정성
- 키-원소 항목들을 정렬할 때 중요한 이슈는 동일 키가 어떻게 처리되느냐는 것
- 두 개의 항목 (Ki, Ei)와 (Kj, Ej)에 대해
- Ki = Kj며 정렬 전에 Ki가 Kj보다 앞서 있었고
- 정렬 후에도 Ki가 앞서있다면 그 정렬은 안정성이 있는 정렬이라고 할 수 있음