Basic Sorting: Bubble, Selection, and Insertion Sort

Tool 1: swapping two values

Think of two glasses: one with calamansi juice, one with Milo. To swap the drinks, you need a third, empty glass.

Here is the swap of arr[j] and the slot after it, arr[j + 1]. You will see these three lines in every sort in this lesson:

 1int temp = arr[j];      // 1. save the left value
 2arr[j] = arr[j + 1];     // 2. copy the right value to the left
 3arr[j + 1] = temp;       // 3. put the saved value on the right

arr[j] = arr[j + 1];     // the left value is overwritten...
arr[j + 1] = arr[j];     // ...so this copies the same value back

Tool 2: a loop inside a loop

Your class schedule has days, and each day has periods. For each day, you go through all its periods before the next day starts.

Here is the schedule as code, with 2 days of 3 periods each:

 1for (int day = 1; day <= 2; day++) {
 2  for (int period = 1; period <= 3; period++) {
 3    System.out.println("Day " + day + ", period " + period);
 4  }
 5}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

It prints six lines. Read the output from top to bottom and watch which number changes faster:

Day 1, period 1
Day 1, period 2
Day 1, period 3
Day 2, period 1
Day 2, period 2
Day 2, period 3

The inner variable (period) goes 1, 2, 3 for each value of the outer variable (day). In total, the inner loop body runs 2 × 3 = 6 times.

In the sorts, the outer loop counts the passes and the inner loop does the comparisons inside one pass.

Bubble sort in Java

The outer loop counts the passes and the inner loop compares the neighbors, just like the nested loop in Part 2. The method is void : it changes the array itself and gives nothing back.

 1static void bubbleSort(int[] arr) { 2  int n = arr.length; 3  for (int i = 0; i < n - 1; i++) {          // one pass 4    for (int j = 0; j < n - 1 - i; j++) {    // each pair of neighbors 5      if (arr[j] > arr[j + 1]) { 6        int temp = arr[j];                   // swap them 7        arr[j] = arr[j + 1]; 8        arr[j + 1] = temp; 9      }10    }11  }12}

Here is how to read the important lines aloud:

Stopping early

Look at pass 4 in the table above: no swaps at all. A pass with no swaps means every neighbor is already in order, so the array is sorted and the remaining passes are wasted work. Many books add a boolean (true or false) variable to stop early:

 1static void bubbleSort(int[] arr) {
 2  int n = arr.length;
 3  for (int i = 0; i < n - 1; i++) {
 4    boolean swapped = false;               // no swaps yet in this pass
 5    for (int j = 0; j < n - 1 - i; j++) {
 6      if (arr[j] > arr[j + 1]) {
 7        int temp = arr[j];
 8        arr[j] = arr[j + 1];
 9        arr[j + 1] = temp;
10        swapped = true;
11      }
12    }
13    if (!swapped) {
14      break;                               // a pass with no swaps: sorted, stop
15    }
16  }
17}

!swapped reads "not swapped" (! flips true and false). On an array that is already sorted, this version makes one pass of n - 1 comparisons and stops. The plain version above still makes all of them. This lesson's walkthroughs and lab use the plain version.

Selection sort in Java

The variable minIndex remembers where the smallest value so far is. The swap happens only once per pass, after the inner loop:

 1static void selectionSort(int[] arr) {
 2  int n = arr.length;
 3  for (int i = 0; i < n - 1; i++) {
 4    int minIndex = i;                   // smallest so far
 5    for (int j = i + 1; j < n; j++) {
 6      if (arr[j] < arr[minIndex]) {
 7        minIndex = j;                   // found a smaller one
 8      }
 9    }
10    int temp = arr[i];                  // swap it to the front
11    arr[i] = arr[minIndex];
12    arr[minIndex] = temp;
13  }
14}

Each pass of the outer loop (line 3) does what one pass did in the steps above. Lines 4 to 9 look through the unsorted part for the smallest value, and lines 10 to 12 are the swap from Part 2, done once at the end of the pass.

Here is how to read the important lines aloud:

 1static void selectionSort(int[] arr) { 2  int n = arr.length; 3  for (int i = 0; i < n - 1; i++) { 4    int minIndex = i;                   // smallest so far 5    for (int j = i + 1; j < n; j++) { 6      if (arr[j] < arr[minIndex]) { 7        minIndex = j;                   // found a smaller one 8      } 9    }10    int temp = arr[i];                  // swap it to the front11    arr[i] = arr[minIndex];12    arr[minIndex] = temp;13  }14}

Insertion sort in Java

The shifting uses a while loop with two conditions joined by && :

 1static void insertionSort(int[] arr) {
 2  for (int i = 1; i < arr.length; i++) {
 3    int key = arr[i];                   // the value to insert
 4    int j = i - 1;
 5    while (j >= 0 && arr[j] > key) {
 6      arr[j + 1] = arr[j];              // shift the bigger value right
 7      j--;
 8    }
 9    arr[j + 1] = key;                   // drop key into the gap
10  }
11}

Each pass of the for loop (line 2) does what one pass did in the steps above. Lines 3 and 4 take out the key and point j at the value on its left. The while loop (lines 5 to 8) shifts the bigger values right, and line 9 drops the key into the gap.

Here is how to read the important lines aloud:

 1static void insertionSort(int[] arr) { 2  for (int i = 1; i < arr.length; i++) { 3    int key = arr[i];                   // the value to insert 4    int j = i - 1; 5    while (j >= 0 && arr[j] > key) { 6      arr[j + 1] = arr[j];              // shift the bigger value right 7      j--; 8    } 9    arr[j + 1] = key;                   // drop key into the gap10  }11}

All three in one program

Here are the three sorts in one runnable file. Run it, and match each output line to its comment:

 1import java.util.Arrays;
 2
 3public class Main {
 4  static void bubbleSort(int[] arr) {
 5    int n = arr.length;
 6    for (int i = 0; i < n - 1; i++) {
 7      for (int j = 0; j < n - 1 - i; j++) {
 8        if (arr[j] > arr[j + 1]) {
 9          int temp = arr[j];
10          arr[j] = arr[j + 1];
11          arr[j + 1] = temp;
12        }
13      }
14    }
15  }
16
17  static void selectionSort(int[] arr) {
18    int n = arr.length;
19    for (int i = 0; i < n - 1; i++) {
20      int minIndex = i;
21      for (int j = i + 1; j < n; j++) {
22        if (arr[j] < arr[minIndex]) {
23          minIndex = j;
24        }
25      }
26      int temp = arr[i];
27      arr[i] = arr[minIndex];
28      arr[minIndex] = temp;
29    }
30  }
31
32  static void insertionSort(int[] arr) {
33    for (int i = 1; i < arr.length; i++) {
34      int key = arr[i];
35      int j = i - 1;
36      while (j >= 0 && arr[j] > key) {
37        arr[j + 1] = arr[j];
38        j--;
39      }
40      arr[j + 1] = key;
41    }
42  }
43
44  public static void main(String[] args) {
45    int[] a = {29, 10, 14, 37, 13};
46    int[] b = {29, 10, 14, 37, 13};
47    int[] c = {29, 10, 14, 37, 13};
48    bubbleSort(a);
49    selectionSort(b);
50    insertionSort(c);
51    System.out.println(Arrays.toString(a));   // [10, 13, 14, 29, 37]
52    System.out.println(Arrays.toString(b));   // [10, 13, 14, 29, 37]
53    System.out.println(Arrays.toString(c));   // [10, 13, 14, 29, 37]
54  }
55}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

Sorting with Java's Arrays

In real programs, you rarely write a sort yourself. Arrays.sort sorts an array of numbers, or of Strings in A-to-Z order, and it uses faster methods like the ones in the next lesson. It lives in java.util.Arrays, so the file starts with an import line.

 1import java.util.Arrays;
 2
 3public class Main {
 4  public static void main(String[] args) {
 5    int[] scores = {29, 10, 14, 37, 13};
 6    Arrays.sort(scores);
 7    System.out.println(Arrays.toString(scores));   // [10, 13, 14, 29, 37]
 8
 9    String[] names = {"Mia", "Ben", "Joy", "Ana"};
10    Arrays.sort(names);                             // A to Z
11    System.out.println(Arrays.toString(names));    // [Ana, Ben, Joy, Mia]
12
13    // Highest first: read the sorted array from the end.
14    for (int i = scores.length - 1; i >= 0; i--) {
15      System.out.print(scores[i] + " ");           // 37 29 14 13 10
16    }
17    System.out.println();
18  }
19}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

Three things to notice:

• Arrays.sort is void, like our sorts: it changes the array itself.
• It always sorts in ascending order. For highest first, read the sorted array from the end (lines 14 to 16).
• For Strings, capital letters come before small letters: "Zed" comes before "ana". Keep names in the same case.