Building Blocks Java

All sorting algorithms rely on two fundamental operations, comparison and swapping. Comparison is straight-forward. Swapping is a little more complex. Consider the following problem. We want to swap the value of a and b. Most people propose something like this as the solution:

class Swap1 {

  public static void main(String args[]) {

   int a = 1;
   int b = 2;

   System.out.println("a = "+a);
   System.out.println("b = "+b);

   // swap a and b

   a = b;
   b = a;

   System.out.println("a = "+a);
   System.out.println("b = "+b);   

  }

}

This produces the following output:

a = 1
b = 2
a = 2
b = 2

That isn’t what you expected! The problem is that we lost track of the value 1 when we put the value of b into a. To correct this we need to introduce a third variable, temp, to hold the original value of a

.

class Swap2 {

  public static void main(String args[]) {

   int a = 1;
   int b = 2;
   int temp;

   System.out.println("a = "+a);
   System.out.println("b = "+b);

   // swap a and b

   temp = a;
   a = b;
   b = temp;

   System.out.println("a = "+a);
   System.out.println("b = "+b);   

  }

}

This code produces the output we expect:

a = 1
b = 2
a = 2
b = 1

Bubble Sort

Now that we’ve learned how to properly swap the values of two variables, let’s proceed to sorting. There are many different sorting algorithms. One of the simplest and the most popular algorithms is referred to as bubble sort. The idea of bubble sort is to start at the top of the array. We compare each element to the next element. If its greater than that element then we swap the two. We pass through the array as many times as necessary to sort it. The smallest value bubbles up to the top of the array while the largest value sinks to the bottom. (You could equally well call it a sink sort, but then nobody would know what you were talking about.) Here’s the code:

import java.util.*;

class BubbleSort {

  public static void main(String args[]) {

   int[] n;
   n = new int[10];
   Random myRand = new Random();

   // initialize the array
   for (int i = 0; i < 10; i++) {
     n[i] = myRand.nextInt();
   }

   // print the array's initial order
   System.out.println("Before sorting:");
   for (int i = 0; i < 10; i++) {
     System.out.println("n["+i+"] = " + n[i]);
   }

   boolean sorted = false;
   // sort the array
   while (!sorted) {
     sorted = true;
     for (int i=0; i < 9; i++) {
       if (n[i] > n[i+1]) {
         int temp = n[i];
         n[i] = n[i+1];
         n[i+1] = temp;
         sorted = false;
       }
     }
   }

  // print the sorted array
  System.out.println();
  System.out.println("After sorting:");
   for (int i = 0; i < 10; i++) {
     System.out.println("n["+i+"] = " + n[i]);
   }

  }

}

In this case we have sorted the array in ascending order, smallest element first. It would be easy to change this to sort in descending order.