Bubble Sort
Bubble sort is one of the simplest sorting algorithm, which compares the adjacent numbers and swap if required.
Given an array of int
, sort them in ascending order. The complexity of the bubble sort algorithm is O(n^2)
.
void bubbleSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
To sort the elements in descending order, just reverse the comparison in if
condition above.
Improvement: The Best Case complexity of the Bubble Sort can be improved to O(n)
using a flag which will detect and decide, should we continue to compare the elements.
void bubbleSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean stop = true;
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
stop = false;
}
if (stop)
break;
}
}
Sign up or log in
Save edit as a guest
Join Stack Overflow
We recognize you from another Stack Exchange Network site!
Join and Save Draft