Cycle Sort

// This implementation assumes that the list contains continuous numbers from `1` to `n`
export function cycleSort(list: number[]) {
  let i = 0;
  // the correct position for `list[i]` will always be `list[i] - 1`
  let position = list[i] - 1;

  while (i < list.length) {
    position = list[i] - 1;

    if (position !== i) {
      // swap
      [list[position], list[i]] = [list[i], list[position]];
    } else {
      i++;
    }
  }

  return list;
}

import { cycleSort } from './cycle-sort';

// Example 1: Permutation of 1 to n
const numbers = [3, 1, 5, 4, 2];
const sorted = cycleSort(numbers);
console.log(sorted); // [1, 2, 3, 4, 5]

// Example 2: Already sorted
const alreadySorted = [1, 2, 3, 4, 5];
cycleSort(alreadySorted); // [1, 2, 3, 4, 5]

// Example 3: Reverse sorted
const reverseSorted = [5, 4, 3, 2, 1];
cycleSort(reverseSorted); // [1, 2, 3, 4, 5]

// Example 4: Single swap needed
const oneSwap = [1, 3, 2, 4, 5];
cycleSort(oneSwap); // [1, 2, 3, 4, 5]

// Example 5: Rotated array
const rotated = [4, 5, 1, 2, 3];
cycleSort(rotated); // [1, 2, 3, 4, 5]

Initial: [3, 1, 5, 4, 2]
         i=0

Step 1: i=0, list[0]=3, position=3-1=2
  3 should be at index 2
  Swap list[0] and list[2]: [5, 1, 3, 4, 2]
  Stay at i=0

Step 2: i=0, list[0]=5, position=5-1=4
  5 should be at index 4
  Swap list[0] and list[4]: [2, 1, 3, 4, 5]
  Stay at i=0

Step 3: i=0, list[0]=2, position=2-1=1
  2 should be at index 1
  Swap list[0] and list[1]: [1, 2, 3, 4, 5]
  Stay at i=0

Step 4: i=0, list[0]=1, position=1-1=0
  1 is in correct position (position == i)
  Move to i=1

Step 5: i=1, list[1]=2, position=2-1=1
  2 is in correct position (position == i)
  Move to i=2

Steps 6-8: All remaining elements are in correct positions
  i=2: list[2]=3 is correct
  i=3: list[3]=4 is correct
  i=4: list[4]=5 is correct

Final: [1, 2, 3, 4, 5]

For n elements:

Worst case writes:
  - Every element in wrong position
  - Each needs one swap (3 writes)
  - At most n-1 swaps
  - Total: 3(n-1) writes

Best case writes:
  - Array already sorted
  - 0 swaps needed
  - Total: 0 writes

This is theoretically optimal!
No comparison-based sort can do better.

export function cycleSort(list: number[]) {
  let i = 0;                    // Current index
  let position = list[i] - 1;   // Target position for current element

  while (i < list.length) {
    // Calculate where list[i] should be
    // For value v in range [1, n], correct index is v-1
    position = list[i] - 1;

    // If element is not in its correct position
    if (position !== i) {
      // Swap it with the element at its target position
      // This moves list[i] to its correct spot and brings
      // a new element to position i for next iteration
      [list[position], list[i]] = [list[i], list[position]];
      // Don't increment i - check the new element at i
    } else {
      // Element is in correct position, move to next
      i++;
    }
  }

  return list;
}

function generalCycleSort(list: number[]) {
  let writes = 0;

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

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

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

    // Skip duplicates
    while (item === list[pos]) pos++;

    // Put the item to its right position
    [list[pos], item] = [item, list[pos]];
    writes++;

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

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

      // Skip duplicates
      while (item === list[pos]) pos++;

      // Put the item to its right position
      [list[pos], item] = [item, list[pos]];
      writes++;
    }
  }

  return list;
}

function findMissingNumber(nums: number[]): number {
  let i = 0;
  
  // Place each number in its correct position
  while (i < nums.length) {
    const pos = nums[i] - 1;
    
    // If number is in range and not in correct position
    if (nums[i] > 0 && nums[i] <= nums.length && nums[i] !== nums[pos]) {
      [nums[i], nums[pos]] = [nums[pos], nums[i]];
    } else {
      i++;
    }
  }
  
  // Find first position where index+1 != value
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return i + 1;
    }
  }
  
  return nums.length + 1;
}