2
$\begingroup$

I have this algorithm ("cyclic sort") to sort an array which contains unique numbers from 1 to $n$:

Input: A[1], ..., A[n]
i ← 1
while i ⩽ n:
  j ← A[i]
  if A[i] ≠ A[j]:
    swap A[i] and A[j]
  else:
    i ← i + 1
  end if
end while

How can I prove that in worst case, the running time of this algorithm is still asymptotically $O(N)$?

My observation:

  • Although $i$ will not increase right after each swap, when it does increase, the next number of required swaps will also decrease.
  • The maximum number of swaps at $i = 1$ will be $N-1$.

Second question is: Is the running time still $O(N)$ if it contains duplicate numbers?

$\endgroup$
4
  • $\begingroup$ Your algorithm doesn't work correctly when the array doesn't consist of the numbers $1,\ldots,n$ in some order. $\endgroup$ – Yuval Filmus Dec 22 '19 at 9:59
  • $\begingroup$ If you’re already sorting 1..n, you might as well just generate 1..n and ignore the input. $\endgroup$ – D. Ben Knoble Dec 22 '19 at 19:49
  • $\begingroup$ @D.BenKnoble The requirement is you have to do it with no extra space, or O(1) in space complexity if you will. Also there're other benefit of doing cyclic sort, detecting missing and duplicated numbers in range of 1 to n for example. $\endgroup$ – Loc Truong Dec 23 '19 at 2:36
  • $\begingroup$ @LocTruong no wasted space if you overwrite the input? Missing/duplicate detection does seem useful, but there are other ways to do that /shrug $\endgroup$ – D. Ben Knoble Dec 23 '19 at 2:51
2
$\begingroup$

We can write each permutation of $1,\ldots,n$ in cycle notation, which will help us understand the behavior of the algorithm.

Suppose that $i = 1$. If $1$ is a fixed point, then the algorithm simply moves on. Otherwise, suppose that the cycle involving $1$ is $(1\;a_2\;a_3\;\cdots\;a_\ell)$, which means that $a_2 = A[1]$, $a_3 = A[2]$, ..., $a_\ell = A[a_{\ell-1}]$ and $1 = A[a_\ell]$. The algorithm will exchange $A[1]$ and $A[a_2]$, so that $A[1] = a_3$ and $A[a_2] = a_2$. This has the effect of removing $a_2$ from the cycle. After $\ell-1$ such steps, the cycle is no more, and $i$ will be increased.

If the permutation has cycles of lengths $\ell_1,\ldots,\ell_r$, then the total number of swaps performed by the algorithm is $(\ell_1-1) + \cdots + (\ell_r-1) = n-r \leq n-1$. This explains your observation that the maximum number of swaps is $n - 1$.

At each iteration of the main loop, either we perform a swap, or we increase $i$. The former can happen at most $n-1$ times, and the latter at most $n$ times. Since each iteration runs in time $O(1)$, in total the algorithm runs in $O(n)$.

$\endgroup$
1
$\begingroup$

We want to swap array elements so that in the end, A[1] = 1, A[2] = 2, ..., A[n] = n.

There are at most n items in the wrong place. Every swap exchanges two elements that are both in the wrong place, and moves at least one into the correct place. After n swaps all elements are in the right place, and at this point there will be no further swaps. Therefore there are at most n swaps.

In each iteration of the loop, there is either a swap, or i is increased. Since the loop is exited when i > n, there are exactly n iterations where i is increased. And there are at most n iterations with a swap. Therefore at most 2n iterations.

$\endgroup$

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.