what is Cycle Sort?

Cycle 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.

Algorithm

Consider an array of n distinct elements. An element a is given, index of a can be calculated by counting the number of elements that are smaller than a.

1. if the element is found to be at its correct position, simply leave it as it is.
2. Otherwise, find the correct position of a by counting the total number of elements that are less than a. where it must be present in the sorted array. The other element b which is replaced is to be moved to its correct position. This process continues until we got an element at the original position of a.

The illustrated process constitutes a cycle. Repeating this cycle for each element of the list. The resulting list will be sorted.

C program

1. #include<stdio.h>  
2. void sort(int a[], int n)  
3. {  
4.     int writes = 0,start,element,pos,temp,i;  
5.    
6.     for (start = 0; start <= n - 2; start++) {  
7.         element = a[start];  
8.         pos = start;  
9.         for (i = start + 1; i < n; i++)  
10.             if (a[i] < element)  
11.                 pos++;  
12.         if (pos == start)  
13.             continue;  
14.         while (element == a[pos])  
15.             pos += 1;  
16.         if (pos != start) {  
17.             //swap(element, a[pos]);  
18.         temp = element;  
19.         element = a[pos];  
20.             a[pos] = temp;    
21.             writes++;  
22.         }  
23.         while (pos != start) {  
24.             pos = start;  
25.             for (i = start + 1; i < n; i++)  
26.                 if (a[i] < element)  
27.                     pos += 1;  
28.             while (element == a[pos])  
29.                 pos += 1;  
30.             if (element != a[pos]) {  
31.               temp = element;  
32.           element = a[pos];  
33.               a[pos] = temp;    
34.                 writes++;  
35.             }  
36.         }  
37.     }  
38.    
39.  }  
40.    
41. int main()  
42. {  
43.     int a[] = {1, 9, 2, 4, 2, 10, 45, 3, 2};  
44.     int n = sizeof(a) / sizeof(a[0]),i;  
45.     sort(a, n);  
46.     printf("After sort, array : ");  
47.     for (i = 0; i < n; i++)  
48.         printf("%d  ",a[i]);  
49.     return 0;  
50. }  

Output:

After sort, array :
1
2
2
2
3
4
9
10
45

Java Program

1. public class CycleSort   
2. {  
3. static void sort(int a[], int n)  
4. {  
5.     int writes = 0,start,element,pos,temp,i;  
6.    
7.     for (start = 0; start <= n - 2; start++) {  
8.         element = a[start];  
9.         pos = start;  
10.         for (i = start + 1; i < n; i++)  
11.             if (a[i] < element)  
12.                 pos++;  
13.         if (pos == start)  
14.             continue;  
15.         while (element == a[pos])  
16.             pos += 1;  
17.         if (pos != start) {  
18.             //swap(element, a[pos]);  
19.         temp = element;  
20.         element = a[pos];  
21.             a[pos] = temp;    
22.             writes++;  
23.         }  
24.         while (pos != start) {  
25.             pos = start;  
26.             for (i = start + 1; i < n; i++)  
27.                 if (a[i] < element)  
28.                     pos += 1;  
29.             while (element == a[pos])  
30.                 pos += 1;  
31.             if (element != a[pos]) {  
32.               temp = element;  
33.           element = a[pos];  
34.               a[pos] = temp;    
35.                 writes++;  
36.             }  
37.         }  
38.     }  
39. }  
40. public static void main(String[] args)  
41. {  
42.     int a[] = { 1, 9, 2, 4, 2, 10, 45, 3, 2 };  
43.     int n = a.length,i;  
44.     sort(a, n);  
45.     System.out.println("After sort, array : ");  
46.     for (i = 0; i < n; i++)  
47.         System.out.println(a[i]);  
48.       
49. }  
50. }  

Output:

After sort, array :
1
2
2
2
3
4
9
10
45

C# Program

1. using System;  
2. public class CycleSort   
3. {  
4. static void sort(int[] a, int n)  
5. {  
6.     int writes = 0,start,element,pos,temp,i;  
7.    
8.     for (start = 0; start <= n - 2; start++) {  
9.         element = a[start];  
10.         pos = start;  
11.         for (i = start + 1; i < n; i++)  
12.             if (a[i] < element)  
13.                 pos++;  
14.         if (pos == start)  
15.             continue;  
16.         while (element == a[pos])  
17.             pos += 1;  
18.         if (pos != start) {  
19.             //swap(element, a[pos]);  
20.         temp = element;  
21.         element = a[pos];  
22.             a[pos] = temp;    
23.             writes++;  
24.         }  
25.         while (pos != start) {  
26.             pos = start;  
27.             for (i = start + 1; i < n; i++)  
28.                 if (a[i] < element)  
29.                     pos += 1;  
30.             while (element == a[pos])  
31.                 pos += 1;  
32.             if (element != a[pos]) {  
33.               temp = element;  
34.           element = a[pos];  
35.               a[pos] = temp;    
36.                 writes++;  
37.             }  
38.         }  
39.     }  
40. }  
41. public void Main()  
42. {  
43.     int[] a = { 1, 9, 2, 4, 2, 10, 45, 3, 2  };  
44.     int n = a.Length,i;  
45.     sort(a, n);  
46.     Console.WriteLine("After sort, array : ");  
47.     for (i = 0; i < n; i++)  
48.         Console.WriteLine(a[i]);  
49.       
50. }  
51. }  

Output:

After sort, array :
1
2
2
2
3
4
9
10
45