• 作者： 林彥君
• 作者服務機構： 台灣工業技術學院電子工程技術系
• 中文摘要： k-排序機是能在O(k)時閒內排好k個項目次序的特殊設備。本論文提出一個特殊的k-排序機。它能在2n步內排好n≦k個項目。若 n>k，則可用它先排好長度k的序列，然後再合併之。k-排序機的運作只要稍做修改，亦可用於合併k個序列。因此可以在2n[logk n]步內排好n>k個項目，其時間是最佳的。本文亦提出三個減少時間的方法，並探討了記憶體的大小對排序時間的影響，而得到一些有用的結果。
• 英文摘要： A κ-sorter is a special-purpose device that can sort κ items in O(κ) time. In this paper, a κ-sorterimplemented with a linear array of processing elements is presented. It is simpler and faster than a previousdesign. It can sort n(<_ κ) items in 2n constant-time steps in the‘zero-time' manner. The κ-sorter, withslightly different operations, can also be used for k-way merging. Thus, we can sort n(> κ) items in 2n[logk n] constant-time steps, which is optimal. Three ways are presented to reduce sorting time. Theeffect of the memory size used on the sorting time is also explored, and useful results regarding the choiceof heap size have been obtained.
• 中文關鍵字： heep; k-sorter, linear array; merging; parallel algorithms; sorting
• 英文關鍵字： --