Generic Cycle Sort in Java
Below is a generic example of the Cycle Sort algorithm in Java. See the Cycle Sort page for more information and implementations.
cycle-sort in Java (Generic)
class CycleSort<T extends Comparable<? super T>> {
public static void main(String[] args)
{
String[] array = {"Andree", "Leana", "Faviola", "Loyce", "Quincy", "Milo", "Jamila", "Toccara", "Nelda", "Blair", "Ernestine", "Chara", "Kareen", "Monty", "Rene", "Cami", "Winifred", "Tara", "Demetrice", "Azucena"};
CycleSort<String> sorter = new CycleSort<>();
sorter.cycleSort(array);
System.out.println(java.util.Arrays.toString(array));
}
void cycleSort(T[] array)
{
// loop from the beginning of the array to the second to last item
for (int currentIndex = 0; currentIndex < array.length - 1; currentIndex++)
{
// save the value of the item at the currentIndex
T item = array[currentIndex];
int currentIndexCopy = currentIndex;
// loop through all indexes that proceed the currentIndex
for (int i = currentIndex + 1; i < array.length; i++)
if (array[i].compareTo(item) < 0)
currentIndexCopy++;
// if currentIndexCopy has not changed, the item at the currentIndex is already in the correct currentIndexCopy
if (currentIndexCopy == currentIndex)
continue;
// skip duplicates
while (item == array[currentIndexCopy])
currentIndexCopy++;
// swap
T temp = array[currentIndexCopy];
array[currentIndexCopy] = item;
item = temp;
// repeat above steps as long as we can find values to swap
while (currentIndexCopy != currentIndex)
{
currentIndexCopy = currentIndex;
// loop through all indexes that proceed the currentIndex
for (int i = currentIndex + 1; i < array.length; i++)
if (array[i].compareTo(item) < 0)
currentIndexCopy++;
// skip duplicates
while (item == array[currentIndexCopy])
currentIndexCopy++;
// swap
temp = array[currentIndexCopy];
array[currentIndexCopy] = item;
item = temp;
}
}
}
}