如何將 Unstable sort 轉為 Stable sort

如何將 Unstable sort 轉為 Stable sort

將原始資料進行轉換，使得具有相同鍵值的資料變成不同，進行排序後再還原回原先的資料。

for i=1 ~ n
a[i] = a[i] * n + ( i-1 )

進行 sort ( 例如使用 selection sort )

for i=1 ~ n
a[i] = a[i] / n ;

全部頂點對最短路徑 (All Pairs Shortest Paths)

A1(3,2) = min { A0(3,2) ， A0(3,1) + A0(1,2) } = min {∞，7}
A1(2,3) = min { A0(2,3) ， A0(2,1) + A0(1,3) } = min {2 ， 6+11}

使用的是 dynamic programming 策略，
就是採用建構式的方法：先建出 A0→ 再建出A1→ ... →An

其中 A0 就是最原始的 cost 矩陣。而 A1 則表示中間點可以經過 節點1
而 A2 則表示中間點可以經過 節點1 ~ 節點2

for i=1 to n
 for j=1 to n
   a[i,j] = cost[i,j];   /* 先把 cost 抄到 A0 之中*/

/* k 放最外面，控制可用的中間點，逐一建構 A0→A1→ ... →An  */
for k=1 to n
{ for i=1 to n              O(n^3)
 { for j=1 to n
   {
     /* 引入 k 當中間點，如果比較近，就改用這條路*/
     if ( a[i,j] > a[i, k] + a[k, j] )
       a[i,j] = a[i, k] + a[k, j];
   }
 }
}

重點提示：

1. 在 A2 的圖中， (i,j) 項的值怎麼算?

不要忘記，A2 的資料是由 A1 為藍本建構而來。
A2(i,j) = min { 原本 A1(i,j) , A1(i,2) + A1(2,j) }
在 A2 中，開放使用節點2，所以要考量，當選擇節點2為中繼時，是否較短路徑。

2. 複雜度與迴圈的設計為何?

迴圈用了 O(n^3) 而最外的計數器是 k 表是當前在建構 Ak 矩陣，
所謂 Ak 矩陣表示目前「中繼節點可用 A1~Ak」
而建構方式是由 A0→A1→...→An 所以 k 會放最外面。

3. 考試的速解法

解題時 A3 矩陣的 (2,1) 欄資料來源會是 (2,3) + (3,1)
不要再傻傻一個一個算了。

Hash function

1. Hash Function
一種資料儲存與擷取技術，用來將 actual key 轉成 hashing address，再依此位置到 hash table 中進行資料的存取。

2. Loading Denisty
α = n / b ；其中 n 為資料數，b 為 bucket 數。

3. 良好的 Hash Function 該具備條件
計算宜簡單，碰撞要少，不要有偏重的問題

4. 常見的 Hash Function 有

Middle Square：將鍵值平方後，取中間某些位元(bits)。
Modulation：除法之後取餘數。
Folding Addition：把數字折疊後相加。

5. Collision
不同的鍵值經由 Hash Function 計算後，對應到相同的 Hashing Address。即：兩個不同鍵值 X、Y，H(X)=H(Y)

6. Overflow
當 Collision 發生時，且無多餘的空間可以存放資料。

7. Overflow 處理方式

(a) linear probing：當 H(x) 發生碰撞時，則延著 H(x)+1、H(x)+2 向下找。
(b) Quadratic Probing：碰撞時改用 [ H(x) ± i^2 ] % n
(c) Double Hashing：碰撞時用 H(x) + i*G(X)；其中 G(X) = R-(X%R) , R為質數
(d) Chaining

8. 使用 Chaining 方法下，平均成功(Sn)、失敗(Un)次數。其中 α = n/b

Sn = 1 + α/2
Un = α

9. Binary Search 與 Hash Function
比較資料要經過排列 || 資料不用經過排列
O(logN) || O(1) 未碰撞時
Actual key search || Transformation key search
不用處理 overflow || 要處理