二維置移排序

Two-Dimensional Homing Sort

王柏易(Bo-Yi Wang)

指導教授 ： 呂學一

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2012年)

https://doi.org/10.6342/NTU.2012.00342

摘要

置移排序是一個自然的排序方法，尤其是當我們用人工的方式排序
時特別有用。一維的置移排序演算法已經被證明可以在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.

並列關鍵字

Sorting ； Permutation ； Discrete Mathematics ； Algorithm

參考文獻

[2] M. Gardner.Time Travel and Other Mathematical Bewilderments. W.H. Freeman & Company, 1987.

[1] S. Elizalde and P. Winkler. Sorting by placement and shift. InProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 68–75, 2009.