BDes2 정렬
정렬 알고리즘 선택표
정렬 알고리즘은 평균 속도만으로 고르기보다 데이터 규모, 거의 정렬된 정도, 안정성, 추가 메모리 요구를 함께 봐야 합니다.
대표 선택지
sorting
insertion
작거나 거의 정렬된 데이터
quick
평균 빠름, pivot 품질 한계
merge
안정 정렬, 추가 메모리 필요
heap
최악 보장, locality는 약함
insertion
→
quick
→
merge
→
heap
정렬 비교 기준
점검
안정성
같은 키의 기존 순서를 보존하는지 봅니다.
최악 시간
입력 패턴이 나쁠 때도 버틸 수 있는지 봅니다.
공간
추가 배열이 허용되는지 확인합니다.
특수 입력
정수 범위가 좁으면 계수/기수 정렬도 고려합니다.