Merge sort(합병 소트): O(nlogn) 단점 O(n)스페이스 필요. Ref-Site
- 반씩 분할하는 divide & conquer 소트의 일종.
- merge_sort (int[] arr, int low, int high) {
int mid=0;
if (low < high) {
mid = (low+high) / 2;
merge_sort(arr, low, mid);
merge_sort(arr, mid+1, high);
merge(arr, low, mid, high); // 이 안에서 스페이스 필요.
}
}
- qSort는 최악에 O(n^2)이지만 실제로는 평균적으로는 qSort가 20%정도 빠르다고 함.
=> qSort 최악의 경우: pivot을 정할때.. pivot이 최대값이면.. 글케 됨.
Radix sort(̧기수 정렬) : Ref-Site
- O(pN) 이며, 2^20(백만개)정도의 숫자를 소팅할때 16진수로 한다고 치면 4자리 수이므로
4번 * N 정도로 할 수 있어 일반 정렬 O(n logn) = O(n * 20) 보다 훨씬 빠른 경우가 발생한다.
Insertion Sort(삽입 정렬): Ref-Site
- O(N^2) 이지만 구현이 매우 간단하고, 길이가 짤을 때 속도가 좋고 안정적이라는 장점이 있다.
c코드-참고
void insertion_sort (int *data, int n ) {
int i, j, remember;
for ( i = 1; i < n; i++ ) {
j=i;
remember = data[i];
while ( --j >= 0 && data[j] > remember)
data[j+1] = data[j]; //쭉 copy
data[j+1] = remember;
}
}
참고: 자바에서는 리스트의 기본 정렬 방식으로
1) Merge Sort를 사용하거나
2) tuned depending on the datatypes Quick Sort를 사용
+ 개체수가 7개 이하일 때 Insertion Sort 방식을 사용한다.
==============Data Structure=================
Heap: complete binary tree (즉 포화트리에서 마지막 자식은 왼쪽노드부터 채움)
최상위 root에는 최소값(Min Heap)이나 최대값(Max Heap)을 관리.
- complete binary tree는 배열로 관리 가능함. h로 관리되겠죠. 2^(h+1) -1 개가 max 노드개수임.
-Priority Queue 가 Heap으로 구현됨.
-median을 구하기에 가장 최적의 자료구조는
바로
Min Heap과 Max Heap을 동시에 하나씩 관리하는 것이다.
예를 들어 100까지의 숫자가 있다면 Max Heap으로 50까지 관리하고, Min Heap을 51부터 관리하면
median이 50 or 51 or 50.5 로 바로 구할 수 있다.
text 추천에 가장 많이 사용되는 변형된 Tree 로서, 마지막 노드에서만 숫자(접근빈도)를 관리한다.
- 일반적으로 Root에는 데이타를 관리하지 않으며, mutliNary tree이다.
- 마지막에 숫자를 관리하지 않아도 서치에는 유용하다. O(L)탐색, 생성은 O(M*L), M은 단어수, L은 가장 긴 단어길이.
참고:
HashTable : O(1+N/B) (B=bucket)
