Common Algorithms
Bubble Sort
Bubble sort repeatedly compares adjacent values and swaps them when they are out of order. It is not a production sorting choice for large data, but it is useful for learning comparison, swapping, and loop behavior.
Basic Implementation
Basic.java
public class Basic {
static 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;
}
}
}
}
public static void main(String[] args) {
int[] numbers = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Before: " + java.util.Arrays.toString(numbers));
bubbleSort(numbers);
System.out.println("After: " + java.util.Arrays.toString(numbers));
}
}
Bubble Sort
A comparison-based sorting algorithm that repeatedly swaps adjacent elements when they are in the wrong order.
Tracing Passes
Tracing each pass makes the loop boundaries and swap decisions visible.
Trace.java
public class Trace {
static void bubbleSortTrace(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
System.out.println("Pass " + (i + 1) + ":");
boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
System.out.printf(" Swap %d and %d%n", arr[j], arr[j + 1]);
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
System.out.println(" Result: " + java.util.Arrays.toString(arr));
if (!swapped) {
System.out.println(" No swaps - array is sorted!");
break;
}
}
}
public static void main(String[] args) {
int[] numbers = ;
System.out.println("Initial: " + java.util.Arrays.toString(numbers));
System.out.println();
bubbleSortTrace(numbers);
}
}
public class Trace {
static void bubbleSortTrace(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
System.out.println("Pass " + (i + 1) + ":");
boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
System.out.printf(" Swap %d and %d%n", arr[j], arr[j + 1]);
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
System.out.println(" Result: " + java.util.Arrays.toString(arr));
if (!swapped) {
System.out.println(" No swaps - array is sorted!");
break;
}
}
}
public static void main(String[] args) {
int[] numbers = ;
System.out.println("Initial: " + java.util.Arrays.toString(numbers));
System.out.println();
bubbleSortTrace(numbers);
}
}
public class Trace {
static void bubbleSortTrace(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
System.out.println("Pass " + (i + 1) + ":");
boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
System.out.printf(" Swap %d and %d%n", arr[j], arr[j + 1]);
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
System.out.println(" Result: " + java.util.Arrays.toString(arr));
if (!swapped) {
System.out.println(" No swaps - array is sorted!");
break;
}
}
}
public static void main(String[] args) {
int[] numbers = ;
System.out.println("Initial: " + java.util.Arrays.toString(numbers));
System.out.println();
bubbleSortTrace(numbers);
}
}
Optimized Version
Optimized.java
public class Optimized {
static int bubbleSortOptimized(int[] arr) {
int n = arr.length;
int passes = 0;
for (int i = 0; i < n - 1; i++) {
passes++;
boolean swapped = false;
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;
swapped = true;
}
}
if (!swapped) {
break;
}
}
return passes;
}
public static void main(String[] args) {
int[] almostSorted = {1, 2, 3, 5, 4, 6, 7, 8};
int[] reversed = {8, 7, 6, 5, 4, 3, 2, 1};
System.out.println("Almost sorted:");
System.out.println("Before: " + java.util.Arrays.toString(almostSorted));
int passes1 = bubbleSortOptimized(almostSorted);
System.out.println("After: " + java.util.Arrays.toString(almostSorted));
System.out.println("Passes: " + passes1);
System.out.println("\nReverse sorted:");
System.out.println("Before: " + java.util.Arrays.toString(reversed));
int passes2 = bubbleSortOptimized(reversed);
System.out.println("After: " + java.util.Arrays.toString(reversed));
System.out.println("Passes: " + passes2);
}
}
Early Termination
If a pass makes no swaps, the array is already sorted and the algorithm can stop early.
Counting Work
Comparisons and swaps show why input order affects bubble sort.
ComparisonCount.java
public class ComparisonCount {
static class SortStats {
int comparisons;
int swaps;
SortStats(int comparisons, int swaps) {
this.comparisons = comparisons;
this.swaps = swaps;
}
}
static SortStats bubbleSortCounted(int[] arr) {
int n = arr.length;
int comparisons = 0;
int swaps = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
comparisons++;
if (arr[j] > arr[j + 1]) {
swaps++;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return new SortStats(comparisons, swaps);
}
public static void main(String[] args) {
int[] sorted = {1, 2, 3, 4, 5};
int[] reversed = {5, 4, 3, 2, 1};
int[] random = {3, 1, 4, 2, 5};
var stats1 = bubbleSortCounted(sorted.clone());
System.out.println("Already sorted: " + stats1.comparisons +
" comparisons, " + stats1.swaps + " swaps");
var stats2 = bubbleSortCounted(reversed.clone());
System.out.println("Reverse sorted: " + stats2.comparisons +
" comparisons, " + stats2.swaps + " swaps");
var stats3 = bubbleSortCounted(random.clone());
System.out.println("Random order: " + stats3.comparisons +
" comparisons, " + stats3.swaps + " swaps");
}
}
Descending Order
Changing the comparison reverses the sort order.
Descending.java
public class Descending {
static void bubbleSortAscending(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;
}
}
}
}
static void bubbleSortDescending(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;
}
}
}
}
public static void main(String[] args) {
int[] numbers1 = {64, 34, 25, 12, 22};
int[] numbers2 = {64, 34, 25, 12, 22};
bubbleSortAscending(numbers1);
System.out.println("Ascending: " + java.util.Arrays.toString(numbers1));
bubbleSortDescending(numbers2);
System.out.println("Descending: " + java.util.Arrays.toString(numbers2));
}
}
Sorting Strings
Bubble sort works on any comparable data when the comparison is defined.
Practical.java
public class Practical {
static void bubbleSort(String[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j].compareTo(arr[j + 1]) > 0) {
String temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
static void bubbleSortCaseInsensitive(String[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j].compareToIgnoreCase(arr[j + 1]) > 0) {
String temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
public static void main(String[] args) {
String[] names = {"Charlie", "Alice", "Bob", "Diana", "Eve"};
String[] mixed = {"apple", "Banana", "cherry", "Date"};
System.out.println("Before: " + java.util.Arrays.toString(names));
bubbleSort(names);
System.out.println("After: " + java.util.Arrays.toString(names));
System.out.println("\nMixed case:");
System.out.println("Before: " + java.util.Arrays.toString(mixed));
bubbleSortCaseInsensitive(mixed);
System.out.println("After: " + java.util.Arrays.toString(mixed));
}
}
Exercise: Practical.java
Implement bubble sort that counts and returns the total number of swaps performed