[Quick Sort]
-
Average Case Complexity
worst case가 pivot이 mininum이거나 maximum일 때 이고, 중간값일 경우에 best case이므로 평균 case일때는 pivot이 1/4n이거나 3/4n 위치에 있을 때이다.
n개의 원소를 partion할 때 각 level에서 걸리는 총 시간 : O(n)
트리의 높이 k는 n(34)^k = 1을 활용해서 k=log4/3n ≤ θ(logn)
따라서 평균 수행시간은 O(n) logn = O(nlogn)
-
In-Place Quick-Sort
in-place 알고리즘? 추가적인 place를 필요로 하지 않는 알고리즘
-> quick-sort에 필요한 L, E, G를 index를 나눔으로써 한 배열에서 분리할 수 있다.
[Merge sort]
- Merge sort 진행 방식 재귀 함수를 사용하여 주어진 배열을 원소가 하나가 될 때까지 나눈다. 그 후 역으로 재귀가 풀리면서 두 배열의 첫 원소를 비교하여 더 작은 원소를 새로운 배열에 넣는 형태로 나누어진 배열들을 병합하여 정렬한다.
- Worst Case Complexity W (n) = W (n/2) + W (n/2) [분할과정에서의 연산 수] + Wmerge (n) (이 때 Wmerge (n) = n-1, W (1) = 0)
