VB6快排,QuickSort

最近我想要一個依文字長度排序的VB6程式,本來是簡單直接寫即可,後來卻看到離職同事所留遺留的一段排序碼並不正確,就感到其實可能不容易。像排序這種號稱簡單的程式,說起來容易寫,但實際上我們經常在工作中發現,花了多少時間在重寫並且重新驗證此程式確實將資料做正確排列。我希望不要浪費這些零碎的時間,所以興起了實作排序的念頭。

我在這週末早上實作了一組有彈性的快速排序演算法,放在GitHub.com網站上,檔案清單如下。

  • /lib/AlgoData.bas
  • /lib/AlgoSort/AlgoSort.bas
  • /lib/AlgoSort/AlgoSortComparison.cls
  • /lib/AlgoSort/AlgoSortHelper.bas

AlgoSort.QuickSort(Unsort() As Variant, …) 是最主要的排序函數。基本的排序方式如下。

Sorted = AlgoSort.QuickSort(Array(5, 2, 7, 3, 6))

如果你有一個陣列為Unsort(7) As String,要排序Unsort陣列時,需要使用AlgoData.CVarArr(AnArray As Variant) 將陣列包裝成 Variant() 。

Dim Unsort(7) As String
Dim Sorted() As Variant
……
Sorted = AlgoSort.QuickSort(AlgoData.CVarArr(Unsort))

使用AlgoSort.QuickSort(…)的第三個參數,可以決定要由小到大排序、或者是由大到小排序。

Sorted = AlgoSort.QuickSort(Array(“aB", “Ab"), ,  _
SortOrderEnum.soeDescending)

第二個參數提供調整比較準則的功能。比較準則是許多排序演算法中使用的基本運算單元,負責判斷二筆資料的大小。AlgoSort的比較準則,由物件類別AlgoSortComparison表示。

Dim c As Comparison
Set c = New Comparison
……
Sorted = AlgoSort.QuickSort(Array(5, 4, 3), c.LessThan,  _
SortOrderEnum.soeAscending)

其實AlgoSort.QuickSort(…)的預設比較準則就是上述的 c.LessThan。比較準則可以自行擴充。要擴充比較準則,只需要修改 AlgoSortComparison.cls ,按照規格撰寫任何你想要的準則。以  LessThan(…) 為例,程式寫成如下。

Public Function LessThan(Optional A As Variant,  _
Optional B As Variant) As Variant
Call AlgoSortHelper.RegisterComparer(  _
A:=A,  _
B:=B,  _
MethodName:=“LessThan",  _
Predicate:=(A < B),  _
ReturnValue:=LessThan)
End Function

我定義的規格,如以下說明所述。

  1. 比較準則必須有二個Variant參數,且二個參數必須是Optional
  2. 比較準則傳回值為Variant型態。
  3. 比較準則的使用權必須為Public
  4. 任何比較準則,當沒有給參數的時候,會傳回一串文字代表函數名稱,而假如參數全給,則會進行比較運算。
  5. 比較準則內,必須使用 AlgoSortHelper.RegisterComparer(…)定義幾個欄位,才是有效的比較準則程式。各種欄位的意義為:
    1. A 欄位必須填 A,同理,B 欄位必須填 B
    2. MethodName欄位決定當本函數沒有取得參數時要傳回什麼函數名稱,所以必須確實填本函數的名稱。
    3. Predicate欄位決定當本函數取得參數名稱時,比較運算要怎麼做,所以必須用到二個參數寫一個邏輯式。
    4. ReturnValue欄位必須填本函數的傳回值變數。

只要正確填寫 AlgoSortHelper.RegisterComparer(…),就可以使用自訂的比較準則,並且使它所應用的排序運算能正常運作。相反地,自訂比較準則可能會寫錯,並且使排序運算出錯、或者使程式無法運作。為了解決算錯和程式當掉等問題,我安排了 AlgoSortHelper.ConfirmMethodName(…) 讓開發者自己做前置檢核。

假設有一位開發者撰寫了以下一段比較準則,加進AlgoSortComparison中,

Public Function MyComparer(Optional A As Variant,  _
Optional B As Variant) As Variant
Call AlgoSortHelper.RegisterComparer(  _
A:=A,  _
B:=B,  _
MethodName:=“MyComparer2″,  _
Predicate:=(A < B),  _
ReturnValue:=LessThan)
End Function

由程式中可見, AlgoSortHelper.RegisterComparer(…) 所登記的MethodName不正確。開發者自己不一定知道是否寫錯。在排序程式中,可以在使用這個比較準則之前,以 AlgoSortHelper.ConfirmMethodName(…) 幫忙找到錯誤並彈出訊息。

Dim c As New Comparison
……
call AlgoSortHelper.ConfirmMethodName(c, c.MyComparer)
Sorted = AlgoSort.QuickSort(Array(1, 2, 3, 4, 5),  _
c.MyComparer)

AlgoSortHelper.ConfirmMethodName(…) 也可以寫在單元測試程式中,讓開發者在軟體釋出之前先發現軟體的錯誤。

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Programming 並標籤為 。將永久鏈結加入書籤。