[자료구조] Comparison Sort, In-place Sort (비교 정렬, 제자리 정렬)

비교 정렬

하나의 추상적인 비교 동작을 통해 목록 요소들을 읽어내는 정렬 알고리즘
데이터들간의 상대적 크기관계만을 이용해서 정렬하는 알고리즘
데이터들간의 크기 관계가 정의되어 있으면 어떤 데이터에든 적용가능
ex) 삽입정렬, 선택 정렬, 거품 정렬, 힙 정렬, 병합 정렬, 퀵 정렬 ...
시간복잡도가 O(nlogn)보다 빠를 수 없음

비비교 정렬

데이터들간의 상대적 크기관계로 정렬하지 않고 데이터에 대한 사전지식을 이용하는 정렬 알고리즘
ex) bucket sort, counting sort, radix sort

제자리 정렬

정렬에 추가적인 메모리 공간이 들지 않음 (거의 무시할 정도의 메모리를 사용)
ex) 삽입, 선택, 버블, 퀵, 힙