排序演算法之研究

Investigation on sorting

曾志鴻(Chih-hung Tzeng)

指導教授 ： 陳維美

大同大學/電機資訊學院/應用數學學系所/碩士(2004年)

摘要

我們先對快速排序、堆積排序、和快速堆積排序的演算法效率的機率性質作徹底分析及模擬；之後，我們並改進了快速堆積排序法，並對其實驗得了些結果；再把改良後的排序法拿來和快速排序法、堆積排序法、快速堆積排序法在交換次數、比較次數、和執行的總時間上作比較。

關鍵字

堆積排序法 ； 快速排序法 ； 排序

並列摘要

In this thesis, we give a systematic study on the stochastic behaviors of heapsort, quicksort, and quickheapsort algorithm, respectively. Moreover, we propose a new variant of quickheapsort, and give experimental results on the performance of the improved quickheapsort. The costs considered include the numbers of swaps, the number of comparisons, and the total time used by quicksort, heapsort, quickheapsort, and the improved quickheapsort.

並列關鍵字

heapsort ； quickheapsort ； quicksort ； sorting

參考文獻

[1] J. L. Bentley, Programming Pearls, Addison-Wesley, 1986.

[2] D.Cantone and G. Cincotti, Quickheapsort, an efficient mix of classical sorting algorithms, CIAC, LNCS 1767, (2000), 150-162.

[4] R.D. Dutton, Weak-heap sort, BIT, 33 (1993), 372-381.

[8] D. E. Knuth, The Art of Computer Programming, volume 3: Sorting and Searching, Addison-Wesley, Reading MA, 1975.

[9] M. D. McIlroy, A killer adversary for quicksort, Software-Practice and Experience, 29:4 (1999), 341-344.