Cycle Sort in Java
Below is an example of the Cycle Sort algorithm in Java. See the Cycle Sort page for more information and implementations.
cycle-sort in Java
public class CycleSort {
public static void main(String[] args)
{
int[] array1 = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
int[] array2 = {2, 1, 5, 2, 9, 1, 2, 3, 3, 4, 4, 5, 6, 7, 8};
CycleSort sorter = new CycleSort();
sorter.cycleSort(array1);
sorter.cycleSort(array2);
System.out.println(java.util.Arrays.toString(array1));
System.out.println(java.util.Arrays.toString(array2));
}
void cycleSort(int[] array)
{
// step 1: loop from the beginning of the array to the second to last item
for (int currentIndex = 0; currentIndex < array.length - 1; currentIndex++)
{
// step 2: save the value of the item at the currentIndex
int item = array[currentIndex];
// step 3: save a copy of the current index
int currentIndexCopy = currentIndex;
// step 4: loop through all indexes that proceed the currentIndex
for (int i = currentIndex + 1; i < array.length; i++)
if (array[i] < item)
currentIndexCopy++;
// step 5: if currentIndexCopy has not changed, the item at the currentIndex is already in the correct position
if (currentIndexCopy == currentIndex)
continue;
// step 6: skip duplicates
while (item == array[currentIndexCopy])
currentIndexCopy++;
// step 7: swap
int temp = array[currentIndexCopy];
array[currentIndexCopy] = item;
item = temp;
// step 8: repeat steps 4, 6 and 7 above as long as we can find values to swap
while (currentIndexCopy != currentIndex)
{
// step 9: save a copy of the currentIndex
currentIndexCopy = currentIndex;
// step 10: repeat step 4
for (int i = currentIndex + 1; i < array.length; i++)
if (array[i] < item)
currentIndexCopy++;
// step 10: repeat step 6
while (item == array[currentIndexCopy])
currentIndexCopy++;
// step 10: repeat step 7
temp = array[currentIndexCopy];
array[currentIndexCopy] = item;
item = temp;
}
}
}
}