Cycle Sort Algorithm
The Cycle Sort Algorithm is a comparison-based, in-place sorting technique that is designed specifically for sorting arrays with a minimal number of writes. It is an unstable sort algorithm that is best suited for situations where the number of writes is a primary concern, such as in memory-constrained environments or when dealing with read-only storage. The basic idea behind the cycle sort algorithm is to partition the array into cycles and sort the elements within each cycle by repeatedly swapping adjacent elements until they reach their correct positions.
The algorithm works by first identifying cycles within the array. A cycle is a group of elements that can be sorted by a series of swap operations, such that each element in the cycle moves to its correct position. To identify a cycle, the algorithm traverses the array, selecting an unsorted element, and repeatedly swaps it with the element in the position it should be in until the initial element reaches its correct position. This process is repeated for each unsorted element in the array until all elements are sorted. The main advantage of the cycle sort algorithm is its ability to minimize the number of writes, making it particularly useful in situations where write operations are limited or costly. However, its relatively slow sorting speed compared to other algorithms makes it less suitable for general-purpose sorting tasks.
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);
}
}
