Understanding Cycle Sort in Java

Introduction

In this article, we will learn about Cycle sort in Java. Cycle sort is a unique sorting algorithm that minimizes the number of writes to the original array, making it useful when write operations are expensive. Unlike other sorting algorithms that may perform numerous swaps, cycle sort ensures that each element is moved to its correct position with minimal write operations.

Working of Cycle Sort

The algorithm operates by finding cycles within the array. For each element, it calculates the number of smaller elements to determine where the element should be placed. If the calculated position is different from the current position, the element is moved to its correct location.

Example

package com.loki.dsa.sorting.blog;
import java.util.Arrays;
public class CycleSort {

    public static void cycleSort(int[] array) {
        int writes = 0;

        // Loop through the array to find cycles to rotate
        for (int cycleStart = 0; cycleStart < array.length - 1; cycleStart++) {
            int item = array[cycleStart];

            // Find position where we put the item
            int pos = cycleStart;
            for (int i = cycleStart + 1; i < array.length; i++) {
                if (array[i] < item) {
                    pos++;
                }
            }

            // If item is already in correct position
            if (pos == cycleStart) {
                continue;
            }

            // Skip duplicates
            while (item == array[pos]) {
                pos++;
            }

            // Put the item to its correct position
            if (pos != cycleStart) {
                int temp = item;
                item = array[pos];
                array[pos] = temp;
                writes++;
            }

            // Rotate rest of the cycle
            while (pos != cycleStart) {
                pos = cycleStart;

                // Find position where we put the element
                for (int i = cycleStart + 1; i < array.length; i++) {
                    if (array[i] < item) {
                        pos++;
                    }
                }

                // Skip duplicates
                while (item == array[pos]) {
                    pos++;
                }

                // Put the item to its correct position
                if (item != array[pos]) {
                    int temp = item;
                    item = array[pos];
                    array[pos] = temp;
                    writes++;
                }
            }
        }
    }
    // Main method to test the implementation
    public static void main(String[] args) {
        int[] array = {1, 8, 3, 9, 10, 10, 2, 4};

        System.out.println("Original array:" + Arrays.toString(array));
        cycleSort(array);
        System.out.println("Sorted array:"+ Arrays.toString(array));
    }
}

Output

Step-by-Step Breakdown

Finding the Position: For each element, the algorithm counts how many elements in the remaining array are smaller than the current element. This count determines the correct position for the element in the sorted array.

Handling Duplicates: When placing an element, if there are duplicates at the target position, the algorithm finds the next available position to maintain stability.

Completing the Cycle: After placing an element, the algorithm continues to place the displaced element until it returns to the starting position, completing one cycle.

Iterating Through All Positions: The process repeats for each starting position in the array until all elements are correctly placed.

Time and Space Complexity

Time Complexity: O(n²) where n is the number of elements. The algorithm requires nested loops to find the correct position for each element.

Space Complexity: O(1) as cycle sort is an in-place sorting algorithm that requires only a constant amount of additional memory.

Summary

Cycle sort represents a specialized sorting algorithm that prioritizes minimizing write operations over speed. While it may not be suitable for general-purpose sorting due to its quadratic time complexity, it excels in specific scenarios where write operations are expensive. Understanding cycle sort provides valuable insight into how different constraints can lead to innovative algorithmic solutions.