請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64890
標題: | 二維置移排序 Two-Dimensional Homing Sort |
作者: | Bo-Yi Wang 王柏易 |
指導教授: | 呂學一(Hsueh-I Liu) |
關鍵字: | 排序,排列,離散數學,演算法, Sorting,Permutation,Discrete Mathematics,Algorithm, |
出版年 : | 2012 |
學位: | 碩士 |
摘要: | 置移排序是一個自然的排序方法,尤其是當我們用人工的方式排序
時特別有用。一維的置移排序演算法已經被證明可以在2^(n-1)-1個步驟以內停止[1]。而我們的主要結果是重新定義二維的置移排序演算法,並且證明在2 n的排列上使用二維置移排序必定會在有限的步驟內停止。 Homing sort, i.e., sorting by placement and shift, is a natural way to do hand-sorting. Elizalde and Winkler showed that (1) anyn-element permutation can be sorted byn 1or less one-dimensional homing operations; (2) non-element permutation admits a sequence of 2^n-1 or more homing operations; and (3) the number ofn-element per-mutations that admit a sequence of 2^(n-1)-1homing operations is super-exponential in n. In the present paper, we study sorting via two-dimensional homing operations and obtain the following obser-vations: (1) Anym npermutation can be sorted by at most mn-1 two-dimensional homing operations. (2) If both vertical-first and horizontal-first homing operations are allowed, for any integers m >= 2 and n >= 2, there is an m npermutation that admits an infinite se-quence of two-dimensional homing operations. (3) If only vertical-first homing operations are allowed, for any integers m >= 3 and n >= 2, there is anm npermutation that admits an infinite sequence of two-dimensional homing operations. (4) The number of 2 x n permutations that admit sequences of (2n) vertical-first two-dimensional homing operations is super-exponential inn. (5) No 2 npermutation admits a sequence of (2n)!or more vertical-first two-dimensional homing op-erations. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64890 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-101-1.pdf 目前未授權公開取用 | 1.45 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。