Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Cycle sort Algorithm

I was browsing through the internet when i found out that there is an algorithm called cycle sort which makes the least number of memory writes.But i am not able to find the algorithm anywhere.How to detect whether a cycle is there or not in an array? Can anybody give a complete explanation for this algorithm?

like image 437
gogo Avatar asked Oct 22 '11 08:10

gogo


People also ask

What is a cyclic sort?

Cycle sort is a comparison sorting algorithm which forces array to be factored into the number of cycles where each of them can be rotated to produce a sorted array. It is theoretically optimal in the sense that it reduces the number of writes to the original array.

What is the best time complexity of cycle sort?

The time complexity of cycle sort is O(n2), even in the best case.

What is Introsort algorithm?

Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance.


1 Answers

The cycle sort algorithm is motivated by something called a cycle decomposition. Cycle decompositions are best explained by example. Let's suppose that you have this array:

4 3 0 1 2

Let's imagine that we have this sequence in sorted order, as shown here:

0 1 2 3 4

How would we have to shuffle this sorted array to get to the shuffled version? Well, let's place them side-by-side:

0 1 2 3 4
4 3 0 1 2

Let's start from the beginning. Notice that the number 0 got swapped to the position initially held by 2. The number 2, in turn, got swapped to the position initially held by 4. Finally, 4 got swapped to the position initially held by 0. In other words, the elements 0, 2, and 4 all were cycled forward one position. That leaves behind the numbers 1 and 3. Notice that 1 swaps to where 3 is and 3 swaps to where 1 is. In other words, the elements 1 and 3 were cycled forward one position.

As a result of the above observations, we'd say that the sequence 4 3 0 1 2 has cycle decomposition (0 2 4)(1 3). Here, each group of terms in parentheses means "circularly cycle these elements forward." This means to cycle 0 to the spot where 2 is, 2 to the spot where 4 is, and 4 to the spot where 0 was, then to cycle 1 to the spot where 3 was and 3 to the spot where 1 is.

If you have the cycle decomposition for a particular array, you can get it back in sorted order making the fewest number of writes by just cycling everything backward one spot. The idea behind cycle sort is to try to determine what the cycle decomposition of the input array is, then to reverse it to put everything back in its place.

Part of the challenge of this is figuring out where everything initially belongs since a cycle decomposition assumes you know this. Typically, cycle sort works by going to each element and counting up how many elements are smaller than it. This is expensive - it contributes to the Θ(n2) runtime of the sorting algorithm - but doesn't require any writes.

like image 131
templatetypedef Avatar answered Oct 22 '22 23:10

templatetypedef