Java/src/main/java/com/sorts/CycleSort.java at Development · iDev-git/Java · GitHub

Repository navigation

History

package com.sorts;

public class CycleSort {

/**

* @param arr Array to be sorted

* @param <T> Generic type

* @return arr Sorted array

public <T extends Comparable<T>> T[] sort(T[] arr) {

int n = arr.length;

// Counter for the number of memory writes

int count = 0;

// Traverse array and put the elements on their respective right places

for (int i = 0; i < n - 1; i++) {

// Initialize item as the starting point

T item = arr[i];

// Find the position where we want to put the item

// Basically we count all the smaller elements to the right of the item

int position = i;

for (int j = i + 1; j < n; j++) {

if (arr[j].compareTo(item) < 0) {

position++;

}

// Check if the element is already at the correct position...

if (position == i) {

// .. then we do not have to do anything

continue;

}

// Ignore duplicate elements

while (item == arr[position]) {

position++;

}

// Put the elements at its right position

if (position != i) {

// Swap

T temp = item;

item = arr[position];

arr[position] = temp;

count++;

}

// Rotate remaining cycle

while (position != i) {

position = i;

// Find the position where we put the element

for (int j = i + 1; j < n; j++) {

if (arr[j].compareTo(item) < 0) {

position++;

}

// Ignore duplicate elements

while (item == arr[position]) {

position++;

}

// Put the element to its correct position

if (item != arr[position]) {

T temp = arr[position];

arr[position] = item;

item = temp;

count++;

}

System.out.println("Number of memory writes :: " + count);

return arr;

}

Java/src/main/java/com/sorts/CycleSort.java at Development · iDev-git/Java · GitHub

Repository navigation

Expand file tree

Breadcrumbs

CycleSort.java

Latest commit

History

Breadcrumbs

CycleSort.java

File metadata and controls