Sorting

Randomize Quicksort note from CLRS

Randomize Quick sort average case run time analysis

• Assume that all input permutation are equally likely.
• 數學證明

Randomize quick sort “worst” run time analysis

• best case

Randomize quick sort “expected” run time analysis

• key point: 相較於average case分析中，假設任何input permutation出現的機率是相同的，在這裡我們直接對input進行permutation（我們來選擇pivot, randomly）
• key point：partition只會被call n次，而每一對element都只會互相比較1次
• O(n + 全部partition過程中比較的次數)

Order Statistics

Selection in Expected Linear Time

Selection in Worst-case Linear Time

Selection in Worst-case Linear Time can ensure QuickSort runs in worst-case nlgn

上圖中灰色區域 node 數量至少為：$3(\lceil \frac{1}{2}\lceil \frac{n}{5}\rceil \rceil -2)$，減掉的 2 分別為自己和有可能多出來的那一組（圖中 x 那組，以及最右邊只有2 個node的那一組）。

如果今天不是切成五個五個一組，而是三個三個的話，同樣的灰色區域 node 數量會大於等於 $2(\lceil \frac{1}{2}\lceil \frac{n}{3}\rceil \rceil -2)\ge \frac{n}{3}-4$，非灰色區域的數量就會是 $\frac{n}{3}+4$，所以遞迴式子會是：$T(n)=T(\lceil \frac{n}{3}\rceil )+T(\frac{2n}{3})+O(n)\Rightarrow T(n)=O(n\lg n)$

Average vs Expected complexity

Average - 只有特定input

The average-case running time not guarantee for the worst- case

i.e. it only applies to a specific input distribution

• the probability is taken over the random choices over an input distribution.

Expected - 所有input

The expected running time guarantee (in expectation) for ++every input++.

• probability is taken over the random choices made by the algorithm.

MIT QUIZ

tags: select,partition

Sort multiset

tags: multiset

:::success

Merge Sort

:::

Counting Inversion

Very Similar Process of Merge Sort

Merge k sorted array each with $\frac{n}{k}$ elements

c-Merge Sort : $T(n)=cT(\frac{n}{c})+O(n\log c)$==$O(n\log c\ast {\log }_{c}n)$==

:::info with the help of min-heap :::

Merge Sort + Insrtion Sort - $T(n)=n\log \frac{n}{k}+O(kn)$

$T(n)=2T(\frac{n}{2})+O(n),n>k$ $O(nk),n\le k$

當size很小的時候，用insertion sort會比較快

Similar Analysis

tags: base case complexity

:::success

Insertion Sort

::: :::info 感覺如果數列具有某種程度上的整齊度，可以使用heap+insertion sort :::

For sorted data : ==$\Omega (n)$==

Suitable for almost sorted data

Example 1

Complexity analysis

${\sum }_{k=1}^{n-1}lglgk=$==$O$==$(nlglgn)=$==$o$==$(nlgn)$

[Improvement]Using Heap

好像不太行，因為距離（$lglgn$）並非固定的，Example 2 就是固定的。

Example 2

Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(nlog k) time

Insertion sort : ==$O(nk)$== Heap : Complexity = $O(k)+O((n-k)logk)=$==$O(nlogk)$==

Which Permutation cause most inversion

Insertion Sort Complexity - ==$O(n+I)$==

$I$ : number of inversion

Insertion Sort with $k$ from original position - ==$O(nk)$==

Insertion Sort with $k$ from original position - ==$O(n\log k)$==

Binary Insertion Sort

找的的確變快了，但是還是要一個個swap到那個位置。 with binary search ：$O(lgk)+O(k)$ without binary search : $O(k)+O(k)$

Pseudo-Time Compexity

If input is not intger

為啥不直接用 hashmap →$\sqrt{n}\lg \sqrt{n}$

tags: multi-set

Build a auxiliary array, and use that auxiliary array’s location as coutning sort data 剛好這題的不同數字的數目很少

:::success

Radix Sort

:::

已經限定是binary representation了，所以不能利用radix sort的優勢 => 更改base

Max set for the same set

tags: bit vector

Delete Duplicate

:::info 感覺消除duplicate時可以考慮用radix sort :::

此題結合物不少觀念

1. 平移range
2. 資料為tuple

Sort n numbers in range from 0 to $n^2$ – 1 in linear time

在sorting的時候，不妨可以看看數字的range，不一定要直接用quicksort/merger/heap sort等等algorithm。使用radix sort說不定可以達到O(n)的速度。

==When radix sort will run in linear? $n^d$ and $d$ is constant==

Radix Sort - Closest Number

Radix Sort – All input orderings give the worst-case running time

Radix Sort–tuple

tags: tuple

Each different size

Each same size

Radix Sort – lexically less than

:::success

Sorting Under Different Scenario

:::

Scenario 1

Scenario 2

Scenario 3

Scenario 4

Randomized Quicksort / Bucket Sort

Randomized Select / Worst Case Linear Time Select

Radix Sort vs Counting Sort

番外篇