《Programming Abstractions in C》學習第75天，p306-p307總結，總計2頁。

一、技術總結

1.Quicksort algorithm(快速排序)

由法國計算機科學家C.A.R(Charles Antony Richard) Hoare（東尼.霍爾）在1959年開發(develop), 1961年發表(publish)。

這里吐槽下維基百科的中文介紹：“在平均狀況下，排序n個項目要O(nlogn)(大O符號)次比較。在最壞情況下則需要O(n^2)次比較，但這種情況并不常見。”——這句話初看顯得莫名其妙，這里的“排序”到底用的是什么排序算法？毫無上下文，難以理解。而英文介紹則好理解得多——“Mathematical analysis of quicksort show that, on average, the algorithm takes O(nlogn) comparisons to sort n items. In the worst case, it makes O(n^2) comparison ”，英文明顯的指出使用的是快速排序。不知道為什么很多中文介紹經常是省略了很多內容。

二、英語總結

1.substantial是什么意思？

答：adj. large in size(sizeable)。p305, Even though the selection sort example makes it cleaar that quadratic algorithms have substantial performance problems (嚴重的性能問題)for large values of N， algorithms whose complexity is O(2^N) are considerably worse。

2.tractable是什么意思？

答：tractare(“to handle, manage”, treat)， adj. easily controlled。p305, As a general rule of thumb(根據經驗)， computer scientists classify problem that can be solved susing algorithms that run in polynomial time as tractable, in the sense that they are amenable to implementation on a computer。

3.demonstrate是什么意思？

答: de-(entirely) + monstrare(point out, show)。 vt. If you could choose the optimal boundary between the small and large elements on each cycle, this algorithm would divide the array in half each time and end up demonstrating(表現出) the same qualitative characteristics. 這里的 end up 后面跟Ving形式，常翻譯成finally(最終)。

4.demarcation是什么意思？

答：

(1)demarcate: de-(from) + marcar(to mark the boundaries of), vt. to show the limit of sth。

(2)demarcation: a board or a rule that show the limit of sth。

p307, For example, a common approach is to pick the first element, which was 56 in the original array, and use it as the demarcation point between small and large element。

四、參考資料

1. 編程

(1)Eric S.Roberts，《Programming Abstractions in C》：https://book.douban.com/subject/2003414

2. 英語

(1)Etymology Dictionary：https://www.etymonline.com

(2) Cambridage Dictionary：https://dictionary.cambridge.org

歡迎搜索及關注：編程人(a_codists)