---
# System prepended metadata
title: 演算法_comparision sort
tags: [大二, 資工]
---
# 演算法_comparision sort
### In-place sorting algorithm
> A sorting algorithm is in-place if the numbers are rearranged within the array A, **with at most a constant number of them sorted outside** the array at any time.
* In-place: Insertion sort, Quicksort, Heapsort
* Not in-place: Merge sort, Counting sort, Radix sort
### worst-case running time
> It is an upper bound on the running time.
> The worst case occurs fair often
> The average case is often as bad as the worst case
### Stable
> keys with same value appear in same order in output as they did in input
* Stable: Insertion sort, Merge sort, Counting sort, Radix sort
* Unstable: Heapsort, Quicksort
### Sorting in Linear Time
> violates the ground rules θ(nlogn)
---
# Insertion sort
* Sorted in place
* Loop invariant
* At the start of each iteration of the for loop of line 1-8, the subarray A[1,..., j – 1] consists of the elements originally in A[1,..., j – 1] but in sorted order
## pseudocode
```!=
Insertion-sort(A)
for j⭠2 to length[A]
do key⭠A[j]
i⭠j-1
while i>0 and A[i]>key
do A[i+1]⭠A[i]
i⭠i-1
A[i]⭠key
```
---
# Merge sort
* NOT in-place
* T(n) = θ(nlogn)
## pseudocode
```!=
MERGE(A, p, q, r)
n1 ⭠ q – p + 1
n2 ⭠ r – q
create array L[1,..., n1 + 1] and R[1,..., n2 + 1]
for i ⭠ 1 to n1
do L[i] ⭠ A[p + i – 1]
for j ⭠ 1 to n2
do R[j] ⭠ A[q + j]
L[n1 + 1] ⭠ ∞ //比較最後一個元素時會用到
R[n2 + 1] ⭠ ∞
i ⭠ 1
j ⭠ 1
for k ⭠ p to r
do if L[i] <= R[j]
then A[k] ⭠ L[i]
i ⭠ i + 1
else A[k] ⭠ R[j]
j ⭠ j + 1
MERGE-SORT(A, p, r)
if p < r
then q ⭠ [(p + r)/2] //取下高斯
MERGE-SORT(A, p, q)
MERGE-SORT(A, q + 1, r)
MERGE(A, p, q, r)
```
---
# Asymptotic notation
* g(n) is an asymptotic **upper bound** for f(n)
O(g(n)) = { f(n) : ∃ positive constants c, n0 s.t. ∀ n ≥ n0, **0 ≤ f(n) ≤ cg(n)**}
o(g(n)) = { f(n) : ∀ constants c>0, ∃ constants n0>0 s.t. ∀ n ≥ n0, 0 ≤ f(n) ==<== cg(n)}
* g(n) is an asymptotic **lower bound** for f(n)
Ω(g(n)) = { f(n) : ∃ positive constants c, n0 s.t. ∀ n ≥ n0, **0 ≤ cg(n) ≤ f(n)**}
ω(g(n)) = { f(n) : ∀ constants c>0, ∃ constants n0>0 s.t. ∀ n ≥ n0, 0 ≤ cg(n) ==<== f(n)}
* g(n) is an asymptotic **tight bound** for f(n)
Θ(g(n)) = { f(n) : ∃ positive constants c1, c2, n0 s.t. ∀ n ≥ n0, 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)}
## Theorem
:::success
f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n))
:::
(⇒):
f(n) = Θ(g(n)) imply ∃ positive constants c1 , c2 , n0 s.t. ∀ n ≥ n0 , 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n),
from 0 ≤ c1g(n) ≤ f(n) , we get f(n) = Ω(g(n)),
from f (n) ≤ c2g(n) , we get f (n) = O(g(n)).
(⇐):
f(n) = O(g(n)) imply ∃ positive constants c1, n1 s.t. ∀ n ≥ n1 , f (n) ≤ c1g(n),
f(n) = Ω(g(n)) imply ∃ positive constants c2, n2 s.t. ∀ n ≥ n2 , 0 ≤ c2g(n) ≤ f(n),
therefore, let n0 = max{n1, n2},
∃ positive constants c1, c2 , n0 s.t. ∀ n ≥ n0 , 0 ≤ c2g(n) ≤ f(n) ≤ c1g(n),
we get that f(n) = Θ(g(n)).
## Properties
#### Transitivity
#### Reflexivity
#### Symmetry
#### Transpose symmetry
## Exmaple
1.
2.
3.
---
# Recurrences
## Substitution method
1. Guess the solution
2. Upper bound、Lower bound
## Recurrence trees
## Master method
> 取最大的，差$lg^{k}n$平手變$lg^{k+1}n$
:::info
T(n) = aT(n/b) + f(n), Where a≥1, b>1, and f(n)>0.
:::
* Case 1：$f(n) < O(n^{log_ba})$
Solution：$T(n) = O(n^{log_ba})$
* ==Case 2：$f(n) = O(n^{log_ba}lg^{k}n),where\ k ≥ 0$== 平手
==Solution：$T(n) = O(n^{log_ba}lg^{k+1}n)$==
* Case 3：$f(n) > O(n^{log_ba})$
Solution：$T(n) = O(f(n))$
---
# Heapsort
* Heap A is a nearly complete **binary tree**
* Height of node = # of edges on a longest simple path from the **node down to a leaf**
* Height of heap = height of root = Θ(lgn)
* Maximum numbers of elements in a heap of height h = $2^{h+1}$ − 1
* property
* Max-heap: for all nodes i, excluding the root, A[PARENT(i)] ≥ A[i].
* Min-heap: for all nodes i, excluding the root, A[PARENT(i)] ≤ A[i].
* A heap can be stores as an array A:
* Root of trees is A[1]
* Parent of A[𝑖] = A[⌊𝑖/2⌋]
* Left child of A[𝑖] = A[2𝑖]
* Right child of A[𝑖] = A[2𝑖+1]
## MAX-HEAPIFY
> 先找自己、左右的child誰最大，最後把最大的換上來
* Time: O(lg n)
```!=
MAX-HEAPIFY(A, i, n)
l ⭠ LEFT(i)
r ⭠ RIGHT(i)
if l ≤ n and A[l] > A[i]
then largest ⭠ l
else largest ⭠ i
if r ≤ n and A[r] > A[largest]
then largest ⭠ r
if largest ≠ i
then exchange A[i]⭤ A[largest]
MAX-HEAPIFY(A, largest, n)
```
## BUILD-MAX-HEAP
> 從最小的子樹走上去
* **Time: O(n)** //Heapify takes a different time for each node
* Loop invariant
* At start of every iteration of for loop, each node i + 1, i + 2,..., n is root of a max-heap
```!=
BUILD-MAX-HEAP(A, n)
for i ⭠ ⌊n/2⌋ downto 1
do MAX-HEAPIFY(A, i, n)
```
## HEAPSORT
> 跟最小的node換，再HEAPIFY
* Time: O(nlgn)
```!=
BUILD-MAX-HEAP(A, n)
for i ⭠ n downto 2
do exchange A[1] ⭤ A[i]
MAX-HEAPIFY(A, 1, i – 1)
```
## Implementation of Priority Queue
### Max Priority Queues
* INSERT(S, x): inserts element x into set S
* 插入新的node，**設為–∞**，再進行HEAP-INCREASE-KEY
* O(lg n)
* MAXIMUM(S): returns elements of S with largest key
* return Root
* Time: Θ(1)
* EXTRACT-MAX(S): removes and returns element of S with largest key
* 把root跟最小node交換，pop largest key，再MAX-HEAPIFY
* Time: O(lg n)
* INCREASE-KEY(S, x, k): increases value of element x’s key to k. Assume k ≥ x’s current key value
* 跟parent比，若key較大就交換
* Time: O(lg n)
```!=
INSERT(A, key, n)
A[n + 1] ⭠ –∞
INCREASE-KEY(A, n + 1, key)
MAXIMUM(A)
return A[1]
EXTRACT-MAX(A, n)
if n < 1
then error “heap underflow”
max ⭠ A[1]
A[1] ⭠ A[n]
MAX-HEAPIFY(A, 1, n – 1)
return max
INCREASE-KEY(A, i, key)
if key < A[i]
then error “new key is smaller than current key”
A[i] ⭠ key
while i > 1 and A[PARENT(i)] < A[i]
do exchange A[i] ⭤ A[PARENT(i)]
i ⭠ PARENT(i)
```
---
# Quicksort
> A[j]小於pivot, i = i+1, A[i]⭤ A[j]
* Sorts in place
* Loop invariant
* Time (Quicksort)
* Worst-case running time: Θ($n^2$)
* Expected running time: Θ(nlg n), constants hidden in are small
* Time (PARTITION): Θ(n)
* For loop iterates exactly r−p times, each iteration takes constant time.
* The section outside the for loop also takes constant time.
* As r−p represents the size of the subarray, PARTITION takes time proportional to the size of the subarray it's called on
```!=
QUICKSORT(A, p, r)
if p < r
then q ← PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)
PARTITION(A, p, r)
x ← A[r]
i ← p – 1
for j ← p to r – 1 //A[r] is pivot
do if A[j] ≤ x // 小於pivot, 換去前面
then i ← i +1
exchange A[i]⭤ A[j]
exchange A[i+1]⭤ A[r]
return i + 1
```
### Performance
#### Worst case
𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑇(0) + 𝑂(𝑛) = **𝑂($𝑛^2$)**
* Have 0 elements in one subarray and n-1 elements in the other subarray
* When input is sorted in either **ascending order** or **descending order**.
* **Insertion sort** runs in O(n) time in this case
#### Best case
T(n) = 2T(n/2) + Θ(n) = **Θ(nlgn)**
* Each subarray has ≤ n/2 elements
#### Balanced case
T(n) ≤ T(9n/10) + T(n/10) + Θ(n) = **O(nlgn)**
* Imagine that PARTITION always produces a 9-to-1 split
## Randomized Quicksort
* an **already-sorted array** causes worst-case behavior in non-randomized QUICKSORT, but not in RANDOMIZED QUICKSORT
* Why analyze the expected running time of a randomized algorithm?
* because it's more representative of **typical time costs**.
* Additionally, considering randomness in computation **prevents adversarial input generation** compared to analyzing all possible inputs
```!=
RANDOMIZED-PARTITION(A, p, r)
i ← RANDOM(p, r)
exchange A[r]⭤ A[i]
return PARTITION(A, p, r)
RANDOMIZED-QUICKSORT(A, p, r)
if p < r
then q ← RANDOMIZED-PARTITION(A, p, r)
RANDOMIZED-QUICKSORT(A, p, q-1)
RANDOMIZED-QUICKSORT(A, q+1, r)
```
### Performance
#### ==Worst case== 必考
* When the (n/4)th smallest element is selected as the pivot using an O(n) time algorithm
* recursion expression is T(n) = T(n/4) + T(3n/4) + cn.
* upon solving the recursion, determine that the time complexity is θ(nlogn)
* Prove that the running time of QUICKSORT is O(n^2) when the array A is sorted in non-increasing order
* the partitioning routine produces one region with n - 1 elements and one region with 1 element
* This results in a recursion tree with a height of O(log n), which gives a worst-case running time of O(n^2)
#### Average-case
---
# Decision tree
* Abstraction of any comparison sort
* counting only comparisons
* Each internal node is labeled by indices of array elements from their original positions
* **Big-O = Decision tree 的樹高 (Root到Leaf最長的Path) = O(n lg n)**
* the smallest possible depth of a leaf in a decision tree for a comparison sort
* n-1 for an input array of length n
* 對一個 leaf 而言，best case 為去比較sort好的數列，只要比較 n-1 次就可以判斷大小順序完成 sorting，其depth 為 n-1(假設 root depth 為 0)
## Theorem
> Any decision tree that sorts n elements has height Ω(nlgn)
> **Heapsort** and **merge sort** are asymptotically optimal comparison sort
* **≧ n!** leaves on the decision tree
* because every permutation appears at least once
* Lemma: Any binary tree of height h has ≦ $2^h$ leaves
* l = # of leaves, h = height, Then l ≦ $2^h$
#### ==Proof== 必考
:::info
l ≧ n!
By lemma, n! ≦ l ≦ $2^h$ or $2^h$ ≧ n!
Take logs: h ≧ lg(n!)
Use Stirling’s approximation: n! ＞ $(n/e)^n$ (by equation (3.16))
h ≧ $lg(n/e)^n$
= n lg(n/e)
= n lg n － n lg e
= Ω( n lg n)
:::
---