1+ // Java program to impleament cycle sort
2+
3+ import java .util .*;
4+ import java .lang .*;
5+
6+ class Cyclesort
7+ {
8+ // Function sort the array using Cycle sort
9+ public static void cycleSort (int arr [], int n )
10+ {
11+ // count number of memory writes
12+ int writes = 0 ;
13+
14+ // traverse array elements and put it to on
15+ // the right place
16+ for (int cycle_start =0 ; cycle_start <=n -2 ; cycle_start ++)
17+ {
18+ // initialize item as starting point
19+ int item = arr [cycle_start ];
20+
21+ // Find position where we put the item. We basically
22+ // count all smaller elements on right side of item.
23+ int pos = cycle_start ;
24+ for (int i = cycle_start +1 ; i <n ; i ++)
25+ if (arr [i ] < item )
26+ pos ++;
27+
28+ // If item is already in correct position
29+ if (pos == cycle_start )
30+ continue ;
31+
32+ // ignore all duplicate elements
33+ while (item == arr [pos ])
34+ pos += 1 ;
35+
36+ // put the item to it's right position
37+ if (pos != cycle_start )
38+ {
39+ int temp = item ;
40+ item = arr [pos ];
41+ arr [pos ] = temp ;
42+ writes ++;
43+ }
44+
45+ // Rotate rest of the cycle
46+ while (pos != cycle_start )
47+ {
48+ pos = cycle_start ;
49+
50+ // Find position where we put the element
51+ for (int i = cycle_start +1 ; i <n ; i ++)
52+ if (arr [i ] < item )
53+ pos += 1 ;
54+
55+ // ignore all duplicate elements
56+ while (item == arr [pos ])
57+ pos += 1 ;
58+
59+ // put the item to it's right position
60+ if (item != arr [pos ])
61+ {
62+ int temp = item ;
63+ item = arr [pos ];
64+ arr [pos ] = temp ;
65+ writes ++;
66+ }
67+ }
68+ }
69+ }
70+
71+ // Driver program to test above function
72+ public static void main (String [] args )
73+ {
74+ int arr [] = {1 , 8 , 3 , 9 , 10 , 10 , 2 , 4 };
75+ int n = arr .length ;
76+ cycleSort (arr , n ) ;
77+
78+ System .out .println ("After sort : " );
79+ for (int i =0 ; i <n ; i ++)
80+ System .out .print (arr [i ] + " " );
81+ }
82+ }
0 commit comments