forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSwapSort.java
More file actions
67 lines (55 loc) · 2.02 KB
/
SwapSort.java
File metadata and controls
67 lines (55 loc) · 2.02 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
59
60
61
62
63
64
65
66
67
package com.thealgorithms.sorts;
import static com.thealgorithms.sorts.SortUtils.*;
/**
* The idea of Swap-Sort is to count the number m of smaller values (that are in
* A) from each element of an array A(1...n) and then swap the element with the
* element in A(m+1). This ensures that the exchanged element is already in the
* correct, i.e. final, position. The disadvantage of this algorithm is that
* each element may only occur once, otherwise there is no termination.
*/
public class SwapSort implements SortAlgorithm {
@Override
public <T extends Comparable<T>> T[] sort(T[] array) {
int LENGTH = array.length;
int index = 0;
while (index < LENGTH - 1) {
int amountSmallerElements = this.getSmallerElementCount(array, index);
if (amountSmallerElements > 0 && index != amountSmallerElements) {
T element = array[index];
array[index] = array[amountSmallerElements];
array[amountSmallerElements] = element;
} else {
index++;
}
}
return array;
}
private <T extends Comparable<T>> int getSmallerElementCount(T[] array, int index) {
int counter = 0;
for (int i = 0; i < array.length; i++) {
if (less(array[i], array[index])) {
counter++;
}
}
return counter;
}
public static void main(String[] args) {
// ==== Int =======
Integer[] a = {3, 7, 45, 1, 33, 5, 2, 9};
System.out.print("unsorted: ");
print(a);
System.out.println();
new SwapSort().sort(a);
System.out.print("sorted: ");
print(a);
System.out.println();
// ==== String =======
String[] b = {"banana", "berry", "orange", "grape", "peach", "cherry", "apple", "pineapple"};
System.out.print("unsorted: ");
print(b);
System.out.println();
new SwapSort().sort(b);
System.out.print("sorted: ");
print(b);
}
}