Arrays in Java: sorting

Continuing our illustration of using arrays, we look at a simple technique for sorting the random numbers in the array into ascending order. In reality, there are better ways of sorting, but the one we're going to use here has the redeeming feature of being easy to understand and only need a few lines of Java.

The basic idea is as follows. Initially, the whole array is "unsorted". We loop through all the positions in the array, going from "left to right" (from zero upwards). So we set up a variable, say, i, which loops from 0 to length (or strictly, length - 1). At each position, we ask the question "what is the next-smallest number out of all those that are still unsorted"? We find that next-lowest number, and swap it with the one in position i. Then, we increase i by 1 and loop round again. At any moment in time, all of the array with positions lower than i is sorted; positions greater than i are not yet sorted, and are the ones that we need to find the next-lowest number from.

First, let's define the loop over i. It'll look as follows:

for (int i = 0; i < randomNumbers.length; i++) {
  int smallestNo = ... smallest number in the array
                   ... with a position greater than 'i'
  int posWithSmallest = ... position of 'smallestNo'
  swap randomNumbers[i] and randomNumbers[posWithSmallest]
}

That's all very well, I hear you ask, but how do we change the lines inside the loop into actual Java code? How do we actually find the number in the array (from position i onwards) that has the lowest number left?

Well, you may have guessed that we need to use a nested loop. That is, inside the loop we've just created step through the array, we'll create another loop that checks all the positions in the array between position i and the end of the array and finds which one is lowest. So the code looks as follows:

for (int i = 0; i < randomNumbers.length; i++) {
  int smallestNo = randomNumbers[i];
  int posWithSmallest = i;
  for (int j = i+1; j < randomNumbers.length; j++) {
    int val = randomNumbers[j];
    if (val < smallestNo) {
      smallestNo = val;
      posWithSmallest = j;
    }
  }
  swap randomNumbers[i] and randomNumbers[posWithSmallest]
}

We start by pretending that the smallest number is the one at position i: notice the two variable declarations of smallestNo and posWithSmallest at the beginning of each pass through the i loop. Then, we go through the rest of the array from position i + 1 onwards, seeing if we can find a smaller value. If we find a smaller value (notice the comparison in the line in bold), then we set smallestNo to be that number, and also posWithSmallest to be its position.

Swapping values round

Finally, to swap the two numbers round— so that the smallest number from the unsorted portion of the array is put in its "rightful place"— we have to be slightly careful. What we logically want to do is as follows:

randomNumbers[i] = smallestNo;
randomNumbers[posWithSmallest] = randomNumbers[i];

However, there's a problem with this. In the first line, we overrite the value in position i, so that in the second line, we end up copying the new value from position i that we've just written, rather than copying the "old" value before it was overwritten. To get round this, we use what is called a temporary variable— that's just a variable that serves in a small number of lines of code:

int tmp = randomNumbers[i];
randomNumbers[i] = smallestNo;
randomNumbers[posWithSmallest] = tmp;

Putting these three lines where we said swap ... in the code above, we you should now find that this code sorts the array.

Efficiency

The program we've written here works in the sense that it produces the correct result. The technique or algorithm that we used is often called a selection sort: at each position of the array, we select from the remaining unsorted values the next one in order. A problem that would often prevent the selection sort from being used in the "real world" is that it doesn't solve the problem efficiently. If you think about it, on each pass through the array, we're likely to end up comparing a lot of pairs of values that we've compared on a previous pass. There are certainly better sorting techniques that avoid this duplication of work. However, they're a bit more complicated to program, which is why we'll leave them for the time being.