-
Notifications
You must be signed in to change notification settings - Fork 214
/
bubble_sort.java
47 lines (39 loc) · 1.72 KB
/
bubble_sort.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
/*
Here's how the Bubble Sort algorithm works:
1. We start by comparing the first two elements of the array. If the first element is greater than the second
element, we swap them.
2. We then compare the second and third elements. If the second element is greater than the third element,
we swap them.
3. We continue this process until we reach the end of the array. At this point, the largest element will
be at the end of the array.
4. We then repeat steps 1-3 for the remaining unsorted portion of the array until the entire array is sorted.
The time complexity of Bubble Sort is O(n^2) in the worst and average case, and O(n) in the best case when
the input array is already sorted.
The space complexity is O(1) as Bubble Sort operates on the input array in-place.
Bubble sort is O(n) on a list that is already sorted i.e. Best case
Sample Input : [2, 1, 9, 3, 5, 4, 0]
Output : [0 1 2 3 4 5 9]
*/
import java.util.Arrays;
public class bubble_sort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
// Traverse through all array elements
for (int i = 0; i < n - 1; i++) {
// Last i elements are already in place
for (int j = 0; j < n - i - 1; j++) {
// Swap adjacent elements if they are in the wrong order
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
}