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) {
  for (let cs = 0; cs < arr.length - 1; cs++) {
    let item = arr[cs], pos = cs;
    for (let i = cs+1; i < arr.length; i++)
      if (arr[i] < item) pos++;
    if (pos === cs) continue;
    while (item === arr[pos]) pos++;
    [arr[pos], item] = [item, arr[pos]];
    while (pos !== cs) {
      pos = cs;
      for (let i = cs+1; i < arr.length; i++)
        if (arr[i] < item) pos++;
      while (item === arr[pos]) pos++;
      [arr[pos], item] = [item, arr[pos]];
    }
  }
} def cycle_sort(arr):
    for cs in range(len(arr) - 1):
        item, pos = arr[cs], cs
        for i in range(cs+1, len(arr)):
            if arr[i] < item: pos += 1
        if pos == cs: continue
        while item == arr[pos]: pos += 1
        arr[pos], item = item, arr[pos]
        while pos != cs:
            pos = cs
            for i in range(cs+1, len(arr)):
                if arr[i] < item: pos += 1
            while item == arr[pos]: pos += 1
            arr[pos], item = item, arr[pos] void cycleSort(vector<int>& arr) {
  for (int cs = 0; cs < (int)arr.size()-1; cs++) {
    int item = arr[cs], pos = cs;
    for (int i = cs+1; i < (int)arr.size(); i++)
      if (arr[i] < item) pos++;
    if (pos == cs) continue;
    while (item == arr[pos]) pos++;
    swap(arr[pos], item);
    while (pos != cs) {
      pos = cs;
      for (int i = cs+1; i < (int)arr.size(); i++)
        if (arr[i] < item) pos++;
      while (item == arr[pos]) pos++;
      swap(arr[pos], item);
    }
  }
} void CycleSort(int[] arr) {
  for (int cs = 0; cs < arr.Length-1; cs++) {
    int item = arr[cs], pos = cs;
    for (int i = cs+1; i < arr.Length; i++)
      if (arr[i] < item) pos++;
    if (pos == cs) continue;
    while (item == arr[pos]) pos++;
    (arr[pos], item) = (item, arr[pos]);
    while (pos != cs) {
      pos = cs;
      for (int i = cs+1; i < arr.Length; i++)
        if (arr[i] < item) pos++;
      while (item == arr[pos]) pos++;
      (arr[pos], item) = (item, arr[pos]);
    }
  }
} void cycleSort(int arr[], int n) {
  for (int cs = 0; cs < n-1; cs++) {
    int item = arr[cs], pos = cs;
    for (int i = cs+1; i < n; i++)
      if (arr[i] < item) pos++;
    if (pos == cs) continue;
    while (item == arr[pos]) pos++;
    int t = arr[pos]; arr[pos] = item; item = t;
    while (pos != cs) {
      pos = cs;
      for (int i = cs+1; i < n; i++)
        if (arr[i] < item) pos++;
      while (item == arr[pos]) pos++;
      t = arr[pos]; arr[pos] = item; item = t;
    }
  }
} 