Algorithms---Java/Sorts/CycleSort.java at master · PrideIceMan/Algorithms---Java · GitHub

History

71 lines (55 loc) · 1.72 KB

Raw

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);

}

Algorithms---Java/Sorts/CycleSort.java at master · PrideIceMan/Algorithms---Java · GitHub

Expand file tree

Breadcrumbs

CycleSort.java

Latest commit

History

Breadcrumbs

CycleSort.java

File metadata and controls