Swap Sorting2018/09/02

I wrote this trying to find the best way to sort a list, only swapping two elements at a time. Turns out I developed a basic theory of permutations with unweildy notation. Lists are permutations, swaps are transpositions, and loops are cycles.

Since a list is bijective, any swap on a list results in a bijection and is a list. The unique identity list of length is denoted as and is defined as .

Corollary 1

Every loop is periodic.

For a given loop of a list of length , if , then since is well defined, . Since is bijective, it is also true that if , then . Suppose there does not exist a where . Then there does not exist a where . Continuing by induction, the loop must have no repeating values. But every value of the infinite loop must be one from the finite set , which is a contradiction. Thus such a exists, and the loop is periodic.

Let be the smallest such , and define the length of a loop to be .

Two loops and are considered equivalent if there exists an where for all . This relation is an equivalence relation, so it can be denoted .

Corollary 2

For any index , .

This follows from and .

Corollary 3

if and only if .

Since , then for some . Then can be applied times.

Corollary 4

If , then where .

This follows from .

Theorem 1

For a given list , if and , then results in a list with exactly more unique loops than in .

Let . By , the number of loops not containing or are the same in both and .

Let be the first index in where . Then for , , but

This indicates that while . Therefore by , and has one more loop than has.

Theorem 2

For a given list , if and , then results in a list with exactly fewer unique loops than in .

Note that where because of and . Then for , and . Thus , and by , . showed that must contain more unique loops than .

and together state that a swap on different indices only increases or decreases the number of loops by .

Corollary 5

A list of length has unique loops if and only if it is .

Since a list of length cannot have more than loops, contains the maximum number of loops.

Corollary 6

A list has a loop with length greater than if and only if it is not .