forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCircleSort.java
More file actions
58 lines (49 loc) · 1.79 KB
/
CircleSort.java
File metadata and controls
58 lines (49 loc) · 1.79 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package com.thealgorithms.sorts;
public class CircleSort implements SortAlgorithm {
/* This method implements the circle sort
* @param array The array to be sorted
*/
@Override
public <T extends Comparable<T>> T[] sort(T[] array) {
if (array.length == 0) {
return array;
}
while (doSort(array, 0, array.length - 1)) {
}
return array;
}
/**
* Recursively sorts the array in a circular manner by comparing elements
* from the start and end of the current segment.
*
* @param <T> The type of elements in the array, which must be comparable
* @param array The array to be sorted
* @param left The left boundary of the current segment being sorted
* @param right The right boundary of the current segment being sorted
* @return true if any elements were swapped during the sort; false otherwise
*/
private <T extends Comparable<T>> boolean doSort(final T[] array, final int left, final int right) {
boolean swapped = false;
if (left == right) {
return false;
}
int low = left;
int high = right;
while (low < high) {
if (array[low].compareTo(array[high]) > 0) {
SortUtils.swap(array, low, high);
swapped = true;
}
low++;
high--;
}
if (low == high && array[low].compareTo(array[high + 1]) > 0) {
SortUtils.swap(array, low, high + 1);
swapped = true;
}
final int mid = left + (right - left) / 2;
final boolean leftHalfSwapped = doSort(array, left, mid);
final boolean rightHalfSwapped = doSort(array, mid + 1, right);
return swapped || leftHalfSwapped || rightHalfSwapped;
}
}