-
Notifications
You must be signed in to change notification settings - Fork 1.8k
/
BubbleSort.java
47 lines (45 loc) · 1.51 KB
/
BubbleSort.java
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
package com.jwetherell.algorithms.sorts;
/**
* Bubble sort is a simple sorting algorithm that works by repeatedly stepping
* through the list to be sorted, comparing each pair of adjacent items and
* swapping them if they are in the wrong order. The pass through the list is
* repeated until no swaps are needed, which indicates that the list is sorted.
* <p>
* Family: Exchanging.<br>
* Space: In-place.<br>
* Stable: True.<br>
* <p>
* Average case = O(n^2)<br>
* Worst case = O(n^2)<br>
* Best case = O(n)<br>
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Bubble_sort">Bubble Sort (Wikipedia)</a>
* <br>
* @author Justin Wetherell <[email protected]>
*/
public class BubbleSort<T extends Comparable<T>> {
private BubbleSort() { }
//@param unsorted array
//@return sorted array
public static <T extends Comparable<T>> T[] sort(T[] unsorted) {
boolean swapped = true;
int length = unsorted.length;
while (swapped) {
swapped = false;
for (int i = 1; i < length; i++) {
if (unsorted[i].compareTo(unsorted[i - 1]) < 0) {
swap(i, i - 1, unsorted);
swapped = true;
}
}
length--;
}
return unsorted;
}
//swapping the value
private static <T extends Comparable<T>> void swap(int index1, int index2, T[] unsorted) {
T value = unsorted[index1];
unsorted[index1] = unsorted[index2];
unsorted[index2] = value;
}
}