[알고리즘] 정렬 정리 및 선택 매뉴얼

ㅇ버블정렬 - 실무에서는 아예 사용하지 말자
"제자리 + stable" O(n^2)
 
 
 
ㅇ선택정렬: 우선순위 큐 (무순 리스트로 구현)
"제자리 + unstable" 
O(n^2): 느리다 - 소규모 입력에 적합
 
 
 
ㅇ삽입정렬: 우선순위 큐 (순서 리스트로 구현)
"제자리 + stable" 
O(n^2): 느리다 - 소규모 입력에 적합
 
 
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
 
 
ㅇ힙정렬: 우선순위 큐 (힙으로 구현)
"제자리 + unstable" 
O(nlog(n)): 빠르다 - 대규모 입력에 적합
 
 
 
ㅇ병합정렬: 분할통치
"제자리 X + stable" 
O(nlog(n)): 빠르다 - 초대규모 입력 + stable 결과에 적합
 
 
 
ㅇ퀵정렬: 분할통치
"제자리 + unstable"
O(nlog(n)): 가장 빠르다 - 웬만한 대규모 입력에 다 적합
 
 
 
 
 
매뉴얼 정리)
아주 간단한 소규모 입력인데 stable여부는 상관없다 -> 선택정렬
아주 간단한 소규모 입력인데 stable을 원한다 -> 삽입정렬
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
대규모 입력인데 stable여부는 상관없다 -> 퀵정렬
대규모 입력인데 stable을 원한다 -> 병합정렬
 
 
 
 
 
 
 
 
 
 
출처 및 참고: 알고리즘-원리와 응용(국형준교수님), Algorithm Design(Jon Kleinberg, Eva Tardos), Foundations of Algorithms using C++(Richard Neapolitan)