Cycle Sort — VisualAlgorithms Docs

How it works

Theoretically optimal in terms of writes. Minimizes the total number of memory writes by rotating elements into their correct positions.
Implementation

      
 function cycleSort(arr, stats) {
  const 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;
    while (item === arr[pos]) {
      pos++;
    }
    if (pos !== cycleStart) {
      [arr[pos], item] = [item, arr[pos]];
      swap(pos, cycleStart);
    }
    while (pos !== cycleStart) {
      pos = cycleStart;
      for (let i = cycleStart + 1; i < n; i++) {
        if (arr[i] < item) pos++;
      }
      while (item === arr[pos]) {
        pos++;
      }
      if (item !== arr[pos]) {
        [arr[pos], item] = [item, arr[pos]];
        swap(pos, cycleStart);
      }
    }
    checkpoint(cycleStart, n - 1);
  }
}
 def cycleSort(arr, stats):
    for cycleStart in range((n - 1)):
        item = arr[cycleStart]
        pos = cycleStart
        for i in range((cycleStart + 1), n):
            if (arr[i] < item):
                pos += 1
        if (pos == cycleStart):
            continue
        while (item == arr[pos]):
            pos += 1
        if (pos != cycleStart):
            arr[pos], item = item, arr[pos]
            swap(pos, cycleStart)
        while (pos != cycleStart):
            pos = cycleStart
            for i in range((cycleStart + 1), n):
                if (arr[i] < item):
                    pos += 1
            while (item == arr[pos]):
                pos += 1
            if (item != arr[pos]):
                arr[pos], item = item, arr[pos]
                swap(pos, cycleStart)
        checkpoint(cycleStart, (n - 1))
 #include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    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;
        }
        while((item == arr[pos])) {
            pos++;
        }
        if((pos != cycleStart)) {
            std::swap(arr[pos], item);
            swap(pos, cycleStart);
        }
        while((pos != cycleStart)) {
            pos = cycleStart;
            for(int i=(cycleStart + 1); i<n; i++) {
                if((arr[i] < item)) {
                    pos++;
                }
            }
            while((item == arr[pos])) {
                pos++;
            }
            if((item != arr[pos])) {
                std::swap(arr[pos], item);
                swap(pos, cycleStart);
            }
        }
        checkpoint(cycleStart, (n - 1));
    }
} public void Sort(int[] arr, int n, dynamic stats) {
    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;
        }
        while((item == arr[pos])) {
            pos++;
        }
        if((pos != cycleStart)) {
            { int _t = arr[pos]; arr[pos] = item; item = _t; }
            swap(pos, cycleStart);
        }
        while((pos != cycleStart)) {
            pos = cycleStart;
            for(int i=(cycleStart + 1); i<n; i++) {
                if((arr[i] < item)) {
                    pos++;
                }
            }
            while((item == arr[pos])) {
                pos++;
            }
            if((item != arr[pos])) {
                { int _t = arr[pos]; arr[pos] = item; item = _t; }
                swap(pos, cycleStart);
            }
        }
        checkpoint(cycleStart, (n - 1));
    }
} #include <stdio.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    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;
        }
        while((item == arr[pos])) {
            pos++;
        }
        if((pos != cycleStart)) {
            { int _t = arr[pos]; arr[pos] = item; item = _t; }
            swap(pos, cycleStart);
        }
        while((pos != cycleStart)) {
            pos = cycleStart;
            for(int i=(cycleStart + 1); i<n; i++) {
                if((arr[i] < item)) {
                    pos++;
                }
            }
            while((item == arr[pos])) {
                pos++;
            }
            if((item != arr[pos])) {
                { int _t = arr[pos]; arr[pos] = item; item = _t; }
                swap(pos, cycleStart);
            }
        }
        checkpoint(cycleStart, (n - 1));
    }
} 