二維置移排序

Abstract

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