Cycle Sorter Algorithm

The Cycle Sort Algorithm is a comparison-based, in-place sorting technique that is designed specifically for sorting arrays with a minimal number of writes. It is an unstable sort algorithm that is best suited for situations where the number of writes is a primary concern, such as in memory-constrained environments or when dealing with read-only storage. The basic idea behind the cycle sort algorithm is to partition the array into cycles and sort the elements within each cycle by repeatedly swapping adjacent elements until they reach their correct positions. The algorithm works by first identifying cycles within the array. A cycle is a group of elements that can be sorted by a series of swap operations, such that each element in the cycle moves to its correct position. To identify a cycle, the algorithm traverses the array, selecting an unsorted element, and repeatedly swaps it with the element in the position it should be in until the initial element reaches its correct position. This process is repeated for each unsorted element in the array until all elements are sorted. The main advantage of the cycle sort algorithm is its ability to minimize the number of writes, making it particularly useful in situations where write operations are limited or costly. However, its relatively slow sorting speed compared to other algorithms makes it less suitable for general-purpose sorting tasks.
using System.Collections.Generic;

namespace Algorithms.Sorters.Comparison
{
    /// <summary>
    /// Cycle sort is an in-place, unstable sorting algorithm,
    /// a comparison sort that is theoretically optimal in terms of the total
    /// number of writes to the original array.
    /// It is based on the idea that the permutation to be sorted can be factored
    /// into cycles, which can individually be rotated to give a sorted result.
    /// </summary>
    /// <typeparam name="T">Type array input.</typeparam>
    public class CycleSorter<T> : IComparisonSorter<T>
    {
        /// <summary>
        /// Sorts input array using Cycle sort.
        /// </summary>
        /// <param name="array">Input array.</param>
        /// <param name="comparer">Integer comparer.</param>
        public void Sort(T[] array, IComparer<T> comparer)
        {
            for (var i = 0; i < array.Length - 1; i++)
            {
                MoveCycle(array, i, comparer);
            }
        }

        private static void MoveCycle(T[] array, int startingIndex, IComparer<T> comparer)
        {
            var item = array[startingIndex];
            var pos = startingIndex + CountSmallerElements(array, startingIndex + 1, item, comparer);

            if (pos == startingIndex)
            {
                return;
            }

            pos = SkipSameElements(array, pos, item, comparer);

            var temp = array[pos];
            array[pos] = item;
            item = temp;

            while (pos != startingIndex)
            {
                pos = startingIndex + CountSmallerElements(array, startingIndex + 1, item, comparer);
                pos = SkipSameElements(array, pos, item, comparer);

                temp = array[pos];
                array[pos] = item;
                item = temp;
            }
        }

        private static int SkipSameElements(T[] array, int nextIndex, T item, IComparer<T> comparer)
        {
            while (comparer.Compare(array[nextIndex], item) == 0)
            {
                nextIndex++;
            }

            return nextIndex;
        }

        private static int CountSmallerElements(T[] array, int startingIndex, T element, IComparer<T> comparer)
        {
            var smallerElements = 0;
            for (var i = startingIndex; i < array.Length; i++)
            {
                if (comparer.Compare(array[i], element) < 0)
                {
                    smallerElements++;
                }
            }

            return smallerElements;
        }
    }
}

LANGUAGE:

DARK MODE: