CS Review: Bubble Sort
Bubble sort is the easiest possible sorting algorithm you could imagine. It works by simply iterating over an array of data and comparing adjacent items. If those items are in the wrong order, then they are swapped. In doing this, the largest items “bubble up” to the correct position in the array (assuming ascending order, anyway).
While this is great from a simplicity standpoint, it’s a pretty awful solution in terms of efficiency. The worst-case performance of bubble sort is O(n2). The best-case turns out to be O(n).
As you can see, this algorithm is not suitable for any sufficiently large datasets.
Implementation
This algorithm is so simple that I think we can just jump right into the implementation without worrying about too much more explanation.
Here’s a bubble sort implementation in Java:
1package com.hackeradam.sorting;
2public class Main {
3 // Performs a bubble sort on a int array
4 public static void bubblesort(int arr[]) {
5 int size = arr.length;
6 int tmp;
7 // This boolean flag is a small optimization
8 // that how long the loop needs to run in some
9 // situations
10 boolean swapped = false;
11 for (int i = 0; i < size - 1; i++) {
12 swapped = false;
13 for (int j = 0; j < size - i - 1; j++) {
14 if (arr[j] > arr[j+1]) {
15 // Swap the items
16 tmp = arr[j];
17 arr[j] = arr[j + 1];
18 arr[j + 1] = tmp;
19 swapped = true;
20 }
21 }
22 // If we didn't need to do a swap in that inner loop
23 // then we must be sorted, so break
24 if (!swapped)
25 break;
26 }
27 }
28 public static void printArray(int arr[]) {
29 for (int i=0; i < arr.length; i++) {
30 System.out.print(arr[i] + " ");
31 }
32 System.out.println();
33 }
34 public static void main(String... args) {
35 int items[] = {5, 2, 88, 100, 3, 0, -1, 20, 30, 7, 99};
36 printArray(items);
37 System.out.println("After bubble sort: ");
38 bubblesort(items);
39 printArray(items);
40 }
41}