有關排序sort

Question

如何在O(N)的時間內，排序range在1到n^2的n個整數

Answer 1

pass1.以(key i) mod n為key實施counting sort或radix sort
這樣執行【range < n => O(n)】

pass2.以[key i / n ] mod n為key實施counting sort或radix sort
這樣執行【range < n => O(n)】


簡單舉例:
range為1~10^2 有11、3、88、50、6、27、23

pass1.
11mod 10= 1
3 mod 10= 3
88 mod 10 = 8
50 mod 10 = 0
6 mod 10 = 6
27 mod 10 = 7
23 mod 10 = 3

進行radix sort的話
50、11、3、23、6、27、88 等於先排個位數

pass2.
[50 / 10] mod 10 = 5
[11 / 10] mod 10 = 1
[ 3 / 10] mod 10 = 0
[23 / 10] mod 10 = 2
[ 6 / 10] mod 10 = 0
[27 / 10] mod 10 = 2
[88 / 10] mod 10 = 8

進行radix sort的話
3、6、11、23、27、50、88 等於再排十位數

時間複雜度: radix sort的時間複雜度為 O(d*(n+r))
(r:基底　n:資料個數　d:最大鍵值位數個數)

再來討論時間複雜度為
O(d*(n+n)) + O(d*(n+n))
= O(dn + dn) + O(dn + dn)
= O(2dn) + O(2dn) 因為d在這可視為常數
= O(n) + O(n)
= O(n)


推廣如果是range 1~100^2的話
例如9812這個數
先從12進行radix sort
再從98進行radix sort
range有幾次方就pass幾回 再實施counting sort或radix sort

因為這不是使用comparison & swap 技巧 所以可以突破 nlogn
以radix sort來說是使用distribution & merge
不過要MAX值確定才可以有linear time sorting method


再來for loop裡面擺n^2 就已經不是O(n)了吧

2007-02-14 15:20:07 補充：
用這個方法
會使用radix sort的話主要是確定最大值位數就夠了
確定最小值在說明O(n)這裡意義不大
不過在寫程式上最小值就有意義

2007-02-14 15:25:43 補充：
就如 Jacob Lee 所說方法很多
個人也沒那麼強
所以在這只用比較基本簡單的sort來說明

Answer 2

#include
#include
#include

int main(int argc, char **argv)
{ int i, n, n2;
int *A, *B;
srand(time(0));
n = 6;
n2 = n * n;
A = (int *) malloc(sizeof(*A) * n);
B = (int *) malloc(sizeof(*B) * n2 + 1);
for (i=1; i<=n2; i++)
B[i] = 0;
for (i=0; i A[i] = rand()%(n*n) +1;
for (i=0; i B[A[i]]++;
for (i=1; i<=n2; i++)
if (B[i]) { printf("%4d", i); B[i]--, i--; }
return 0;
}

2007-02-13 13:19:13 補充：
第一個 Loop：清為 0。
這是這個方法的大問題：它要O(n^2)！

第二個 Loop：產生亂數，O(n)，但，不應計時。

第三個 Loop：排序！
這應該是 O(n) 排序的唯一解！
我見過好幾次，沒見過另外的解法。

第四個 Loop：顯示答案。

main( ) 裡的 int argc, char **argv 可以去掉

你老師應該是忘了要把 n^2 的部份去掉！
因為我見過的 O(n) sort 的唯一解，是在 constant range, 不是在 n^2 range。

2007-02-13 13:20:56 補充：
你老師應該是忘了要把 n^2 的部份去掉！(我是指時間。)

你若是碩士，要小心畢業考時的一題：
　這方法為何可以突破 O( n log n) 的上限？
要準備好如何回答！

2007-02-13 13:41:17 補充：
應該說：其它見過的解法都是這解法的變化。
　不是沒見過其它的解法。

2007-02-13 13:43:25 補充：
要是沒有人在這裡解出來，而你的老師後來有公佈真正 O(n) 的 sort，請在意見處告知。
謝謝。

2007-02-14 07:35:38 補充：
#include
#include
#include

2007-02-14 07:35:44 補充：
int **dim2(int x, int y)
{ int *buf, **A, i, j;
if ( A = (int **) malloc(sizeof(int*) * y) ) // if (!NULL)
if ( buf = (int *) malloc(sizeof(int) * x * y) )
{ for (j=i=0; i else { free(A); A=0; } // Can not alloc the 2nd, free the 1st

return A;
}

2007-02-14 07:37:44 補充：
int main(int argc, char **argv)
{ int i, j, k, n;
int *A, *B, *S, **V;

srand(time(0));

if (argc==2) n = atoi(argv[1]);
if (n < 2 || n > 999) n = 5;

A = (int *) malloc(sizeof(*A) * n);
for (i=0; i for (i=0; i printf("\n");

2007-02-14 07:43:34 補充：
V = dim2(n, n 1); // 索引陣列
B = (int *) malloc(sizeof(*B) * (n 1)); // 索引陣列使用量
S = (int *) malloc(sizeof(*S) * n); // 排序後儲存在這

2007-02-14 07:46:32 補充：
// 第一次排序：耗時 O(3n) = O(n)
for (i=0; i<=n; i ) B[i] = 0; // 索引用量為0, O(n)

for (i=0; i { j = A[i]%n;
V[j][B[j] ] = A[i]; }

for (i=j=0; i<=n && j { for (k=0; k S[j ] = V[i][k]; }

2007-02-14 07:48:04 補充：
// 第二次排序：耗時 O(n)。註解同上。
for (i=0; i<=n; i ) B[i] = 0;
for (i=0; i { j = S[i]/n;
V[j][B[j] ] = S[i]; }
for (i=j=0; i<=n && j { for (k=0; k A[j ] = V[i][k]; }

2007-02-14 07:55:15 補充：
for (i=0; i
return 0;
}

這種 sort (radix sort) 需要：
　1. 已知數值上下限。（光知道上限不夠）
　2. 數值總數有上限且不會太大。
如：
　3 ~ 9 這是有上下限。（上面 1. 在說的是這個）
但還得要是　　　　　（以下是 2. 在說的）
　3, 4, 5, 6, 7, 8, 9
或
　3.0, 3.1, 3.2, ..., 8.9, 9.0
不可以是〝實數〞

2007-02-14 07:58:59 補充：
我忘了可以給它來個 2次、n次。

但，我也有說：for (n^2) 就已經不是O(n)了

2007-02-14 08:02:53 補充：
第二次補上的程式，是類似 online 的方法，只是稍再簡單一點：
　先把每個值按 Ai % n去排序。
　再把每個值按 Ai / n 去排序。（不用 [(Ai / n) %n]）

2007-02-14 08:29:59 補充：
不是用比較來排序的排序法至少有：
　格子排序法 (Pigeonhole sort)
　水桶排序法 (Bucket sort)
　計數排序法 (Counting sort)
　LSD基數排序法 (Least Significant Dight first Radix sort)
　MSD基數排序法 (Most Significant Dight first Radix sort)
　延伸排序法(Spread sort)
這類排序法多數至少在最差狀況下是 O(n)；
Bucket sort 甚至在最差狀況下還是 O(n)！
所以，方法其實很多。