Cycle Sort Program with Explanation and Code

2025-11-19 cycle sort minimal writes sort in-place sorting permutation cycle sort python cycle sort c cycle sort php cycle sort js cycle sort csharp cycle sort efficient write sorting algorithm

Cycle Sort is an in-place sorting algorithm designed to minimize the number of writes to memory. This page includes a clear explanation and complete working code in Python, C, JavaScript, PHP, and C#—ideal for learning about efficient memory-write sorting algorithms.

Program Explanation

What is Cycle Sort?

Cycle Sort is an in-place, comparison-based sorting algorithm that minimizes the total number of writes to the array. It works by identifying cycles in the permutation of elements and rotating these cycles to place elements into their correct positions. Cycle Sort is optimal when write operations are costly, such as memory with limited write cycles (e.g., EEPROM, Flash).

Steps to Solve

  1. Iterate through the array and treat each index as the start of a cycle.
  2. Find the correct index where the current element should go.
  3. If the element is already in the correct position, skip the cycle.
  4. Otherwise, place the element in its correct position by swapping.
  5. Repeat the process for the displaced element until the entire cycle completes.
  6. Continue this for all elements in the array until fully sorted.

Key Points

  • Minimizes number of writes — only writes when necessary.
  • Time complexity: O(n²) in worst case.
  • Useful when write operations are expensive.
  • Works in-place and does not use extra memory.
  • Not stable (relative order is not preserved).
  • Optimal in terms of minimal memory writes.

Program Code


def cycle_sort(arr):
    n = len(arr)

    for cycle_start in range(0, n - 1):
        item = arr[cycle_start]

        pos = cycle_start
        for i in range(cycle_start + 1, n):
            if arr[i] < item:
                pos += 1

        if pos == cycle_start:
            continue

        arr[pos], item = item, arr[pos]

        while pos != cycle_start:
            pos = cycle_start
            for i in range(cycle_start + 1, n):
                if arr[i] < item:
                    pos += 1

            arr[pos], item = item, arr[pos]

arr = list(map(int, input("Enter numbers: ").split()))
cycle_sort(arr)
print("Sorted array:", arr)
      

#include <stdio.h>

void cycleSort(int arr[], int n) {
    for (int cycle_start = 0; cycle_start < n - 1; cycle_start++) {
        int item = arr[cycle_start];
        int pos = cycle_start;

        for (int i = cycle_start + 1; i < n; i++)
            if (arr[i] < item)
                pos++;

        if (pos == cycle_start)
            continue;

        int temp = arr[pos];
        arr[pos] = item;
        item = temp;

        while (pos != cycle_start) {
            pos = cycle_start;
            for (int i = cycle_start + 1; i < n; i++)
                if (arr[i] < item)
                    pos++;

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

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    cycleSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function cycleSort(arr) {
  let n = arr.length;

  for (let cycleStart = 0; cycleStart < n - 1; cycleStart++) {
    let item = arr[cycleStart];
    let pos = cycleStart;

    for (let i = cycleStart + 1; i < n; i++)
      if (arr[i] < item) pos++;

    if (pos === cycleStart) continue;

    [arr[pos], item] = [item, arr[pos]];

    while (pos !== cycleStart) {
      pos = cycleStart;
      for (let i = cycleStart + 1; i < n; i++)
        if (arr[i] < item) pos++;

      [arr[pos], item] = [item, arr[pos]];
    }
  }
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
cycleSort(arr);
console.log("Sorted array:", arr);
      

using System;

class Program {

    static void CycleSort(int[] arr) {
        int n = arr.Length;

        for (int cycleStart = 0; cycleStart < n - 1; cycleStart++) {
            int item = arr[cycleStart];
            int pos = cycleStart;

            for (int i = cycleStart + 1; i < n; i++)
                if (arr[i] < item)
                    pos++;

            if (pos == cycleStart)
                continue;

            int temp = arr[pos];
            arr[pos] = item;
            item = temp;

            while (pos != cycleStart) {
                pos = cycleStart;
                for (int i = cycleStart + 1; i < n; i++)
                    if (arr[i] < item)
                        pos++;

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

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        CycleSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function cycleSort(&$arr) {
    $n = count($arr);

    for ($cycle_start = 0; $cycle_start < $n - 1; $cycle_start++) {
        $item = $arr[$cycle_start];
        $pos = $cycle_start;

        for ($i = $cycle_start + 1; $i < $n; $i++)
            if ($arr[$i] < $item)
                $pos++;

        if ($pos == $cycle_start)
            continue;

        $temp = $arr[$pos];
        $arr[$pos] = $item;
        $item = $temp;

        while ($pos != $cycle_start) {
            $pos = $cycle_start;
            for ($i = $cycle_start + 1; $i < $n; $i++)
                if ($arr[$i] < $item)
                    $pos++;

            $temp = $arr[$pos];
            $arr[$pos] = $item;
            $item = $temp;
        }
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
cycleSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>
1