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;
            }
        }
    }
}

Discussion