Edison.X. Blog

關於排序與搜尋，演算法多到不行，記得自學過程中，花一星期時間實作完十多種排序演算法，有些演算法做起來蠻複雜的，最後該忘的還是忘得差不多。

這裡要講的不是所有 sort 、search 演算法細節，而是 stdlib.h 裡面提供的兩隻寫好的 function - qsort、bsearch。

compare function

這兩支在調用時，都必須先寫一個 compare function，做為 callback 使用，該 compare function 格式固定為

int compare_function(const void*, const void*);

要轉型的話在該 function 裡強制轉型，否則無法正常調用。以較簡單的 int 型態而言，比較函式長如此

int comp_func(const void* a, const void* b)
{
    return (*(int*)a-*(int*)b);
}

若要由大排到小的話，只需改成  return (*(int*)b-*(int*)a); 即可。而較複雜的 struct 也可進行自定義的比較，此部份不贅述。同時為了方便起見，變數假設為下

int main()
{
    const int Size = 10;
    int arr[10] = {1,5,3,2,4,8,10}; // Cnt=7
    int *pos, n, Cnt=7;
    const int key1=5, key2=9;

    return 0;
}

qsort

qsort 放在表頭檔 stdlib.h (cstdlib) 裡面，使用前必須強調，它是 un-stable sort，使用時注意。在調用 qsort 時，語法很簡單

// qsort
    puts("\n> --------- qsort ---------- \n");
    qsort((void*)arr, Cnt, sizeof(*arr), comp_func);

第一個參數即為 arr，第二個參數為元素個數，第三個參數為每個元素多大，第四個參數便為剛剛給的 compare_function。

調用完後，再將 arr 做輸出，發現 arr 裡之元素都已排序完成。

bsearch

bsearch 放在 stdlib.h (cstdlib) 裡面，為二分搜尋法，調用上與 qsort 大同小異，唯多了一個 key 參數。使用前，必須保證該 array 是有序排序。

    n   = Cnt;
    pos = bsearch((const void*)&key1, (const void*)arr, n, sizeof(int), comp_func);
    if(pos==NULL) printf("> can't find key %d\n", key1);
    else printf("find key %d at pos %d\n", key1, pos-arr);

    n   = Cnt;
    pos = bsearch((const void*)&key2, (const void*)arr, n, sizeof(int), comp_func);
    if(pos==NULL) printf("> can't find key %d\n", key2);
    else printf("find key %d at pos %d\n", key2, pos-arr);

於陣列中沒找到該鍵值時，將傳回  NULL，否則將傳回指向該鍵值之指標。

* lfind

lfind 為線性搜尋法 (也就是從 arr[0] 一直慢慢找到 arr[n-1] )，目前這隻函式沒被放到標準裡面，少數 compiler (VC) 裡有支援，使用前不需進行排序，VC 是放在 search.h 裡。使用方式與 bsearch 似，但 bsearch 第三個參數是放 size of array (陣列大小)，雖 lfind 第三個參數也是放 size of array，但必須以 pointer 方式傳入。

    n = Cnt;
    pos = (int*)lfind((void*)&key1,arr,&n,sizeof(*arr),comp_func);
    if(pos==NULL) printf("> can't find key %d\n", key1);
    else printf("> find key %d at pos %d\n", key1, pos-arr);

    n = Cnt;
    pos = (int*)lfind((void*)&key2,arr,&n,sizeof(*arr),comp_func);
    if(pos==NULL) printf("> can't find key %d\n", key2);
    else printf("> find key %d at pos %d\n", key2, pos-arr);

* lsearch

lsearch 使用的也為線性搜尋，也是非標準，VC 放在 search.h 裡。使用方式與 lfind 一模一樣，但有個重要的特性不一樣。

當 lfind 找不到元素值時，將會傳回 NULL，而 lsearch 找不到元素值時，會在陣列的最後一筆資料後面，再加上這筆鍵值，

同時返回新增鍵值之指標。故使用 lsearch 時，最好確定 array 至少還有一個元素的空間可以增加，否則易造成寫入錯誤。

    pos = (int*)lsearch((void*)&key1,arr,&n,sizeof(*arr),comp_func);
    if(pos==arr+Cnt) printf("> can't find key %d\n", key1);
    else printf("> find key %d at pos %d\n", key1, pos-arr);

    pos = (int*)lsearch((void*)&key2,arr,&n,sizeof(*arr),comp_func);
    if(pos==arr+Cnt) printf("> can't find key %d\n", key2); // add element to the end.
    else printf("> find key %d at pos %d\n", key2, pos-arr);

* 效率高？

關於 qsort 與 bsearch 比自己寫的效率還高，這論點筆者保留 (其實是持反對，但懶得實測，所以沒證據的情況下才說 "保留" ) 。

目前在 vc 逐步 trace 情況下，release mode 下進不了 qsort 與 bsearch ，而在 debug mode 下其實查得到 qsort 與 bsearch 和其它兩隻之 source code，扣除掉安全性，其實和一般演算法裡學的 qsort、bsearch 沒什麼兩樣。但相對的，這兩支函式必須塞 compare function pointer，在做 callback 動作時，筆者認為動作是較慢的。

但上述筆者提到，那是在 debug mode 情況下，而 visual c++ runtime library，筆者只知道 debug mode 與 release mode 所調用的 library (dll) 並不相同，故這兩隻函式在 release mode 是否會有不同寫法，使得結果更快，目前除了實測 wall time 外，倒不知如何查證。

還有另一點，微軟的 qsort 應還有考慮其他一般 coder 沒考慮到的因素，約半年前在某論壇裡，看到有人直接 copy 微軟的 qsort 出來改，效果比調用的還快 (這筆者也沒留數據與原參考網址)。

另若真在意 sort 與 search 之效率問題，又不想自己造輪子，可考慮直接使用 c++ , algorithm header，裡面已有 sort、find、binary_search 等寫好的 template library。提一下，STL 裡面的 sort ，用的是 IntroSort，比 qsort 稍佳。另 algorithm 裡之這些 library，善用的話確實比 qsort 與 bsearch 快些，理由這裡不贅述 ( 不贅述的理由也是怕筆者說得不夠清楚，怕誤導)， 要數據的話可以再自己實測，或 google " Sorting in C++ vs C"  與 "qsort STL sort"，可得到不少訊息，找到的數據，大概都圍繞在 STL 裡之 sort快 2~3 倍左右。