AlgorithmsInJava/Sorts/CycleSort.java at master · csbase/AlgorithmsInJava

71 lines (55 loc) · 1.72 KB

package Sorts;

import static Sorts.SortUtils.less;
import static Sorts.SortUtils.print;

/** @author Podshivalov Nikita (https://github.com/nikitap492) */
class CycleSort implements SortAlgorithm {

  @Override
  public <T extends Comparable<T>> T[] sort(T[] arr) {
    int n = arr.length;

    // traverse array elements
    for (int j = 0; j <= n - 2; j++) {
      // initialize item as starting point
      T item = arr[j];

      // Find position where we put the item.
      int pos = j;
      for (int i = j + 1; i < n; i++) if (less(arr[i], item)) pos++;

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

      // ignore all duplicate elements
      while (item.compareTo(arr[pos]) == 0) pos += 1;

      // put the item to it's right position
      if (pos != j) {
        item = replace(arr, pos, item);
      }

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

        // Find position where we put the element
        for (int i = j + 1; i < n; i++)
          if (less(arr[i], item)) {
            pos += 1;
          }

        // ignore all duplicate elements
        while (item.compareTo(arr[pos]) == 0) pos += 1;

        // put the item to it's right position
        if (item != arr[pos]) {
          item = replace(arr, pos, item);
        }
      }
    }

    return arr;
  }

  private <T extends Comparable<T>> T replace(T[] arr, int pos, T item) {
    T temp = item;
    item = arr[pos];
    arr[pos] = temp;
    return item;
  }

  public static void main(String[] args) {
    Integer arr[] = {4, 23, 6, 78, 1, 26, 11, 23, 0, -6, 3, 54, 231, 9, 12};
    CycleSort cycleSort = new CycleSort();
    cycleSort.sort(arr);

    System.out.println("After sort : ");
    print(arr);
  }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Expand file tree

Search code, repositories, users, issues, pull requests...

Uh oh!

FilesExpand file tree

CycleSort.java

Latest commit

History

CycleSort.java

File metadata and controls

Expand file tree