Java Bubble sort example
Bubble sort is the simplest sorting algorithm, it compares the first two elements, if the first is greater than the second, swaps them, continues doing (compares and swaps) for the next pair of adjacent elements. It then starts again with the first two elements, compares, swaps until no more swaps are required.
1. Explanation
#unsorted data -> [99, 88, 55, 77, 1, 66] #1 iteration. #1.1 -> [99, 88, 55, 77, 1, 66] -> [88, 99, 55, 77, 1, 66] #1.2 -> [88, 99, 55, 77, 1, 66] -> [88, 55, 99, 77, 1, 66] #1.3 -> [88, 55, 99, 77, 1, 66] -> [88, 55, 77, 99, 1, 66] #1.4 -> [88, 55, 77, 99, 1, 66] -> [88, 55, 77, 1, 99, 66] #1.5 -> [88, 55, 77, 1, 99, 66] -> [88, 55, 77, 1, 66, 99] #2 iteration. #2.1 -> [88, 55, 77, 1, 66, 99] -> [55, 88, 77, 1, 66, 99] #2.2 -> [55, 88, 77, 1, 66, 99] -> [55, 77, 88, 1, 66, 99] #2.3 -> [55, 77, 88, 1, 66, 99] -> [55, 77, 1, 88, 66, 99] #2.4 -> [55, 77, 1, 88, 66, 99] -> [55, 77, 1, 66, 88, 99] #3 iteration. #3.1 -> [55, 77, 1, 66, 88, 99] -> [55, 77, 1, 66, 88, 99] {no swap} #3.2 -> [55, 77, 1, 66, 88, 99] -> [55, 1, 77, 66, 88, 99] #3.3 -> [55, 1, 77, 66, 88, 99] -> [55, 1, 66, 77, 88, 99] #4 iteration. #4.1 -> [55, 1, 66, 77, 88, 99] -> [1, 55, 66, 77, 88, 99] #4.2 -> [1, 55, 66, 77, 88, 99] -> [1, 55, 66, 77, 88, 99] {no swap} #5 iteration. #5.1 -> [1, 55, 66, 77, 88, 99] -> is_sorted = true, break;
Here’s the Java bubble sort implementation.
public static void sort(int[] input) {
int inputLength = input.length;
int temp;
boolean is_sorted;
for (int i = 0; i < inputLength; i++) {
is_sorted = true;
for (int j = 1; j < (inputLength - i); j++) {
if (input[j - 1] > input[j]) {
temp = input[j - 1];
input[j - 1] = input[j];
input[j] = temp;
is_sorted = false;
}
}
// is sorted? then break it, avoid useless loop.
if (is_sorted) break;
System.out.println("\n");
}
}
2. Java Bubble sort example
A full example to demonstrate the use of bubble sort algorithm to sort a simple data set, support ascending order or descending order.
BubbleSortExample.java
package com.mkyong;
import java.util.Arrays;
import java.util.stream.Collectors;
public class BubbleSortExample{
public static void main(String[] args) {
int[] array = {99, 88, 55, 77, 1, 66};
System.out.print("unsorted data: ");
printArray(array);
System.out.print("ascending order: "); //1,55,66,77,88,99
bubble_sort(array);
printArray(array);
System.out.print("descending order: "); //99,88,77,66,55,1
bubble_sort(array, false);
printArray(array);
}
private static void bubble_sort(int[] input) {
bubble_sort(input, true);
}
private static void bubble_sort(int[] input, boolean ascending) {
int inputLength = input.length;
int temp;
boolean is_sorted;
for (int i = 0; i < inputLength; i++) {
is_sorted = true;
for (int j = 1; j < (inputLength - i); j++) {
if (ascending) {
if (input[j - 1] > input[j]) {
temp = input[j - 1];
input[j - 1] = input[j];
input[j] = temp;
is_sorted = false;
}
} else {
if (input[j - 1] < input[j]) {
temp = input[j - 1];
input[j - 1] = input[j];
input[j] = temp;
is_sorted = false;
}
}
}
// is sorted? then break it, avoid useless loop.
if (is_sorted) break;
}
}
private static void printArray(int[] data) {
String result = Arrays.stream(data)
.mapToObj(String::valueOf)
.collect(Collectors.joining(","));
System.out.println(result);
}
}
Output
unsorted data: 99,88,55,77,1,66
ascending order: 1,55,66,77,88,99
descending order: 99,88,77,66,55,1
I think, for second loop (inputLength – i) should be only inputLength. Tried with {10, 8, 99, 7, 1, 5, 88, 9}.
thanks for this wonderful post.
I applaud the publication of your article on Java part. It’s a good reminder to look on the real time content. http://bit.ly/LearnHadoop