2
$\begingroup$

Copy from Wikipedia

Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.

Why does cycle sort have minimum write times (or minimum swap times)? I can't find such a claim in the paper Cycle-Sort: A Linear Sorting Method. I have met different variants of cyclesort, so I want to know the specific proof method.

Edited: I misunderstood minimum write times with minimum swap times, so the premise of the problem is wrong.

$\endgroup$
5
  • 1
    $\begingroup$ Before we can prove a theorem, we need a precise formulation of it. What is the computation model? What exactly are we counting? $\endgroup$ Mar 14, 2022 at 11:16
  • $\begingroup$ Based on th description of the algorithm in the Wikipedia article you gave, the algorithm moves an element once, to its correct position, if needed. If this movement requires displacing another element, this other element is the next element to be relocated to its right position. This is repeated until all elements are in place. $\endgroup$
    – Russel
    Mar 14, 2022 at 11:23
  • 2
    $\begingroup$ Wikipedia contains a complete proof of minimality: "Each value is either written zero times, if it's already in its correct position, or written one time to its correct position. This matches the minimal number of overwrites required for a completed in-place sort." $\endgroup$ Mar 14, 2022 at 11:46
  • 2
    $\begingroup$ You could also come up with an algorithm that minimizes the number of swaps, though this seems to be different from the algorithm described by Wikipedia. The minimum number of swaps is $n$ minus the number of cycles (where $n$ is the length of the array). This is minimal since it's the same as the number of transpositions which multiplies to the permutation, and every transposition reduces the number of cycles by at most 1. $\endgroup$ Mar 14, 2022 at 11:47
  • $\begingroup$ Please don't use "Edited:". There is no need to mark what has changed. Instead, revise the question so it reads well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755. If you asked the wrong question, and realize this after you have already received an answer to the wrong question, then please don't change the question after the fact. Instead, it is better to ask a new question, and make the new question self-contained. $\endgroup$
    – D.W.
    Mar 15, 2022 at 20:16

1 Answer 1

6
$\begingroup$

Cycle sort minimizes the number of times that a value is written to the array, as proved in the Wikipedia article:

Each value is either written zero times, if it's already in its correct position, or written one time to its correct position. This matches the minimal number of overwrites required for a completed in-place sort.

Another implementation of cycle sort only uses swaps. Sorting a cycle of length $\ell$ requires $\ell-1$ swaps (this includes the special case of a fixed point, in which $\ell=1$), for a total of $n-c$ swaps, where $c$ is the number of cycles. This is optimal. Indeed, denote the initial permutation of the array by $\pi$, and the swaps applied to it by $\sigma_1,\ldots,\sigma_m$. Thus $$ \sigma_m \cdots \sigma_1 \pi = \mathsf{id}, $$ implying that $\pi = \sigma_1 \cdots \sigma_m$. It remains to show that if we write $\pi$ as a product of transpositions, then there at least $n-c$ transpositions in the product. Indeed, since the identity permutation has $n$ cycles and multiplying by a transposition reduces the number of cycles by at most $1$, any such product must contain at least $n-c$ transpositions.

$\endgroup$
2
  • $\begingroup$ In addition, the swap version of cyclesort apply to arraylist without duplicates. $\endgroup$
    – Voyager
    Mar 14, 2022 at 12:10
  • $\begingroup$ In a language like C++ with objects as array members, having a move constructor to move the cycle elements can be a major gain if you have otherwise expensive constructors and destructors. $\endgroup$
    – gnasher729
    Mar 15, 2022 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.