fbpx

他發明了 QuickSort !Tony Hoare :我最初只想加快查字典!

當你有一大堆數字的時候,要怎樣才能夠最快把它們由最小到最大一一排序?一個好的排序法可以節省不少的時間、人力及電力,而公認最快速的排序法為 QuickSort  (快速排序法)。這個聽名字就很霸氣的排序法,是由東尼·霍爾 (Tony Hoare) 所提出。



為了可以更快查字典,他發明了 QuickSort

東尼·霍爾 (Tony Hoare) 生於英國錫蘭可倫坡,英國計算機科學家,圖靈獎得主。他設計了快速排序演算法、霍爾邏輯、交談循序程式。他在五十年代初對電腦產生興趣,雖然他在牛津大學主修哲學。1958年從軍隊中退伍後,回到了牛津大學,研讀統計學,取得學士後學位。在此期間,開始學習程式設計,他跟着 Leslie Fox 學習 Autocode。

為了學習俄語,他以英國文化協會的交換學生身份,至蘇聯莫斯科國立大學留學,研究了語言的機器翻譯及概率論。發明 Quicksort 的原因竟然是,在他查找字典單詞時,覺得目前的排序算法仍然太慢,為了有效地查找字典中的單詞,他提出了眾所周知的排序算法 QuickSort。

在莫斯科州立大學學習期間,接受了國家物理實驗室(NPL)的工作機會,開始從俄語到英語的機器翻譯項目。但是,字典存儲在磁帶上,他需要在翻譯前按照字母順序排列一個句子的單詞。霍爾想到了解決這個問題的兩種方法:第一種方法將花費與句子長度的平方成正比的時間量。第二種方法稍後將顯示為快速排序。那時,他只認識一種語言,Mercury Autocode。

不幸的是,他發現無法使用 Mercury Autocode 成功編寫 QuickSort代碼。於是,他回到英國後,他找到了一份小型電腦製造商Elliott Brothers的工作,而他的第一個任務是編寫Shell sort algorithm。在霍爾完成這個任務後,他告訴老闆,他認為他知道一個更快的方法,但他老板認為這是不可能的。1961年,霍爾在布萊頓參加了一個Algol 60級課程,在這個過程中,霍爾編寫了一個超快排序算法,現在稱為 quick sort。

Quicksort 到底有多快?

對於排序法有興趣的大家,不妨看一看這片段。

片中比較了各類排序法的演算速度,而在中間的 QuickSort 在大部分情況下都是最快的,而畫面左下方Bubble Sort明顯一直是最最最慢的。

這是因為QuickSort採用「分而治之、各個擊破」的觀念,從數列中挑出一個元素,稱為 pivot ,並以它作標準重新排序數列,所有比 Pivot 小的元素擺放前面,所有比 Pivot 大的元素擺在後面(相同的數可以到任何一邊)。重覆這個步驟,就可以把平均運算速度加速至 O (n log n) 。

QuickSort能夠提升數據處理上的效率,亦非常適合用於大型數據集和內存受限的情況。甚至可能在你的電腦或者手機中,按字母或數字排列的列表都是用 Quicksort 進行排序。而這個想法,只是當年東尼·霍爾為了快速查字典而提出來的。

QuickSort是計算機科學 (Computer Science )的一個重大突破,他獲得了圖靈獎,他是英國皇家學會院士,有爵士頭銜,亦獲頒馮諾曼獎。

而這個目前最常用排序法之一的發明者東尼·霍爾,仍然是一個低調謙虛的人(編輯找資料的時候幾乎找不到他的訪談及介紹)。在我們找到的其中一篇訪談中,他曾提及,他沒有任何研究生學位 (Postgraduate Degree),所以能夠發明 QuickSort是「因為自己夠幸運」。(Since I did not have any postgraduate degree, it was very lucky that I discovered quicksort. )他也太謙虛了吧?事實上 Quick Sort作為一種排序算法也相當出色,市場上的主要對手 Merge Sort 在理想情況下能平分秋色,當然最終要看看運氣,如果 Pivot 選得不好的話……

而作為一名學者,三十多年來,霍爾通過諮詢,教學和合作研究項目與業界保持著密切的聯繫。他現在是劍橋大學首席研究員及牛津大學榮譽退休教授,大家想體驗這個算法的話,編輯會推薦大家到這個網站玩一玩。

資料來源:cs.ox 、cs.stanford

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *

限制時效已用盡。請重新載入驗證碼。