Comparison Sort
- 데이터들간의 상대적 크기관계만을 이용해서 정렬하는 알고리즘
- 따라서 데이터들간의 크기 관계가 정의되어 있으면 어떤 데이터에든 적용 가능(문자열, 알파벳, 사용자 정의 객체)
- 종류
: 버블소트, 삽입정렬, 합병정렬, 퀵소트, 힙정렬 등
Non-comparison Sort
- 정렬할 데이터에 대한 사전지식을 이용 - 적용에 제한
- 종류
: Bucket sort, Radix sort
정렬문제의 하한
- 하한(Lower bound)
- 입력된 데이터를 한번씩 다 보기 위해서 최소 O(n)의 시간복잡도 필요
- 합병정렬과 힙정렬 알고리즘들의 시간복잡도는 O(nlog2n)
- 어떤 comparison sort 알고리즘도 O(nlog2n)보다 나을 수 없다.
- 시간복잡도
| O(n^2) | O(nlogn) |
|---|---|
| Selection sort, Bubble sort, Insertion sort, Quicksort | Merge sort, Heap sort |
📚 참고
Photo by Michael Dziedzic on Unsplash
protect me from what i want