Iteration: Selection Sort

Sorting arrays of integers

As mentioned in the previous set of notes, sorting a collection of data in some order is one of the most common things done with computers. Although Java offers us many ways of storing a collection of data in its library of code through its Collection interface, the array concept is still widely used. Arrays have been found in programming languages since the early days of programming, and they are a basic concept in many programming languages because they directly reflect the way data could be stored in a reserved block of computer memory. As it happens, the Java library provides us with built-in sorting methods for arrays in the class Arrays. So we need not write such methods ourselves. However, as computer scientists it is important that we know how sorting works. Sorting algorithms also serve as a good illustration of more general concepts associated with algorithms.

In order to concentrate on basic sorting, we will discuss sorting arrays of integers. Even here, we need to express the order in which we are sorting the array of integers. We cannot sort anything without having the concept of an order over the data items we are sorting. It might seem obvious that sorting an array of integers means sorting into the arrangement with the lowest integer first, the second lowest second, and so on. But this is sorting in "ascending numerical order". Thinking about this, it's obvious we could also sort in "descending numerical order" (highest first). It requires a little more thought to think of other orders on numbers. What about sorting "in order of closeness to 100", so 95 comes before 108 but after 102, for example? Or "sorting in ascending order of the number of prime factors", so that 285 (3×5×19) comes before 210 (2×3×5×7) but after 221 (13×17)? For simplicity, we will assume for the present that "sorting an array of integers" means sorting it in ascending numerical order.

An Iterative Sorting Algorithm

The following sorting algorithm, called selection sort, uses iteration. Its main advantage is that it is simple to explain and fairly intuitive:

Find the position of the smallest item in the array, swap that item with the first item in the array.
Find the position of the smallest item in the portion of the array apart from the first element, swap that item with the second item in the array.
Find the position of the smallest item in the portion of the array apart from the first and second elements, swap that item with the third item in the array.
And so on until we are looking at just the last two items in the array.
Now the array is sorted.

As an example, consider the following array:

After the first step of the algorithm, the 2 will be swapped with the 5, since 2 is the smallest integer in the array. This gives the situation:

As 2 is the smallest integer in the array, it is now in its correct position for the array with its elements rearranged so as to be sorted in ascending numerical order. The next step swaps the 3 with the 9, giving:

The vertical line through the array here indicates that at this point in the algorithm, the array can be considered divided into two parts, the part to the left of the line which stores the elements in their orders and places for the final arrangement of the array, and the part to the right, which contains the remaining elements of the array in no particular order. Each step in the algorithm moves the line one space to the right, so the next step (swapping 7 and 4) gives:

The next step involves finding the smallest element in the part of the array to the right of the line, and swapping it with the first element to the right of the line. As it happens, the smallest element to the right of the line is the first element to the right of the line, so it is "swapped with itself", in other words no change. However, moving to the next step of the algorithm can be considered as moving the line on, giving:

The next step swaps the 7 with the 6, giving:

The step after that swaps the 7 with the 9, giving:

Now everything to the left of the line is its place for the final sorted form of the array, and there is only one integer to the right of the line, which must be the highest integer, so the whole array is sorted.

Developing Code for the Algorithm

When writing the code to implement an algorithm, the first step to take is to consider the signature of the method that will implement the algorithm. You need to consider what are the arguments it takes and what is the value it returns.

In this case, there is a slight trickiness involved because the algorithm doesn't actually return anything. It acts by changing the values in the array which is passed to it as an argument rather than by creating a new array and returning it. So its return type is given as void meaning "nothing returned". As we are dealing with arrays of integers, the type of the method's argument is int[]. In short general purpose methods dealing with arrays, it's conventional to name the array just a, which we shall do so here. However, you should be aware that it is good programming practice when writing methods for more specific purposes to use meaningful variable names, and avoid one-letter variable names. We now have the following signature for the method: 

public static void sort(int[] a)
It is declared as static because we assume this method will be called on its own and not attached to some object.

Looking at the algorithm, we can see there is a general pattern, and we need to express this in terms of a loop. On each step round the loop, we look for the smallest element in that portion of the array from the ith element to the last element in the array, and we swap that element with the ith element. This gives us the following for the partially developed code: 

public static void sort(int[] a)
{
 for(int i=0; i<a.length-1; i++)
    {
     int pos = position of smallest element in array from position i
     swap ith position of array with posth position of array
    }
}
Again, while one-letter variable names should mostly be avoided, it's a common convention that a variable used as an index to an array is called i, or if that variable name has already been used to index another array, j, in circumstances where the piece of code where the variable is used is not very long and there's no particular meaning to the variable except that it's an array index.

The parts in italics above indicate where what is written needs further developing until it becomes Java code. One easy way of dealing with this is to make it calls to new Java methods which do the required work, this then leaves us with the separate issue of writing the code for the new Java methods. The methods are declared as private because they are introduced only to help us develop our sort method, so there is no need to make them available to anyone else. We also add comments describing what each method does, giving is: 

public static void sort(int[] a)
// Sort the contents of array a in ascending numerical order
{
 for(int i=0; i<a.length-1; i++)
    {
     int pos = smallestPosFrom(i,a);
     swap(a,i,pos);
    }
}

private static int smallestPosFrom(int from,int[] a)
// Return the index of the smallest element in the section of
// array 'a' from that indexed 'from' to the end of the array

private static void swap(int[] a,int pos1, int pos2)
// Swap the elements indexed pos1 and pos2 within array a
Here, swap, like sort works by changing the array it takes as an argument, so its return type is void. What we need to do is change the values stored in the array cells, so that after a call to the method a[pos1] stores what a[pos2] stored before, and a[pos2] stores what a[pos1] stored before. We can't just do this by: 
a[pos1] = a[pos2];
a[pos2] = a[pos1];
because the first assignment here will copy what is in a[pos2] into a[pos1], thus losing the old value of a[pos1] altogether, leaving us with two copies of what was originally in a[pos2]. So the correct code for the method swap employs a local variable to act as a temporary storage for the old value of a[pos1] so this can be copied into a[pos2]: 
private static void swap(int[] a,int pos1, int pos2)
// Swap the elements indexed pos1 and pos2 within array a
{
 int temp;
 temp = a[pos1];
 a[pos1] = a[pos2];
 a[pos2] = temp;
}
When considering smallestPosFrom, it is important to note that it returns the index of the smallest integer in the section of the array starting at the ith element, and not the smallest integer itself. A common source of errors when dealing with arrays of integers is to confuse the integers stored in the arrays with the integers used to index the arrays. The algorithm to find the smallest integer in the section of the array starting at the ith element requires a local variable which stores the index of the smallest element found so far, which is initially i, but is replaced by the index of smaller elements as they are found. Here's the code: 
private static int smallestPosFrom(int from,int[] a)
// Return the index of the smallest element in the section of
// array 'a' from that indexed 'from' to the end of the array
{
 int pos=from;
 for(int i=from+1; i<a.length; i++)
    if(a[i]<a[pos])
       pos=i;
 return pos;
}
The loop invariant here is that the variable pos is set such that a[pos] is the smallest integer in the section of array a between and including position from and up to but not including position i. This holds at the start of the loop, since then i is from+1, so there is only integer in the section, so it must be the lowest, and pos set to from indexes it. At any time round the loop, if this loop invariant is true, then either the next integer in the array is smaller than the one indexed by pos in which case pos is changed to index that integer, so the loop invariant continues to hold after i is increased by 1, or the next integer in the array is not smaller than a[pos], so the loop invariant still holds after i is increased by 1. When the loop finishes, i must have the value a.length, and as the loop invariant must hold, pos must be the index of the smallest integer in the section of array a starting at position from and continuing to the end of the array.

As a minor point, the names of the variables in the comment to the method smallestPosFrom are surrounded by single quotes. This is to avoid confusion between the word "from" and the variable name from.

Complete Code and Testing Method for the Algorithm

So here's the complete code for the algorithm which sorts arrays of integers in the way described above, plus a main method which enables it to be tested from Linux: 
import java.io.*;
class SortIntArrayIt1
{

 public static void main(String[] args)
 throws IOException
 {
  int n;
  int[] array;
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  System.out.print("Enter number of integers : ");
  n = Integer.parseInt(in.readLine());
  array = new int[n];
  for(int i=0; i<n; i++)
     {
      System.out.print("Enter integer "+i+": ");
      array[i] = Integer.parseInt(in.readLine());
     }
  System.out.println("The array you entered is:");
  System.out.println(arrayToString(array));
  sort(array);
  System.out.println("After sorting, the array is:");
  System.out.println(arrayToString(array));
 }

 private static String arrayToString(int[] a)
 {
  String str="[";
  if(a.length>0)
     {
      str+=a[0];
      for(int i=1; i<a.length; i++)
         str+="|"+a[i];
     }
  return str+"]";
 }

 public static void sort(int[] a)
 // Sort the contents of array a in ascending numerical order
 {
  for(int i=0; i<a.length-1; i++)
     {
      int pos = smallestPosFrom(i,a);
      swap(a,i,pos);
     }
 }

 private static int smallestPosFrom(int from,int[] a)
 // Return the index of the smallest element in the section of
 // array 'a' from that indexed 'from' to the end of the array
 {
  int pos=from;
  for(int i=from+1; i<a.length; i++)
     if(a[i]<a[pos])
        pos=i;
  return pos;
 }

 private static void swap(int[] a,int pos1, int pos2)
 // Swap the elements indexed pos1 and pos2 within array a
 {
  int temp;
  temp = a[pos1];
  a[pos1] = a[pos2];
  a[pos2] = temp;
 }
}
The variable referring to the array in the main method is called array. This is permissible in Java, because the word array is not reserved as a key-word, so can be used as a variable name. It is necessary to ask in advance how many integers will be in the array, since when an array object is created in Java you have to declare the number of elements in it, and that number can't be changed. However, an array variable can refer to arrays of any size, so the size of the array is fixed when the program is run (run-time) and not when the program is written and compiled (compile-time).

In order to be able to display the array, a separate method which takes an array of integers and returns a string, called arrayToString is given. The string will consist of the characters for the numbers of the array in the order they are in the array, separated by commas, and with square brackets surrounding the whole. You cannot expect Java to "know" how to display an array of integers. Making the code to display an array into a separate method helps break down the code to easily understood small parts, and enables this code to be re-used, first to display the original array, then to display the array after it is sorted. It is more flexible, and in keeping with the way Java does things, for the method to return a string which can be printed than for it to do the printing itself.

For comparison, below is a version of the sort method in which the code for the algorithm is run together into one method rather than spread across several methods: 

public static void sort(int[] a)
// Sort the contents of array a in ascending numerical order
{
 for(int i=0; i<a.length-1; i++)
    {
     int temp,pos=i;
     for(int j=i+1; j<a.length; j++)
        if(a[j]<a[pos])
           pos=j;
     temp = a[i];
     a[i] = a[pos];
     a[pos] = temp;
    }
}
This is just another way of expressing the same algorithm. Because the code isn't broken up into methods with meaningful name, it's harder when looking at it to understand what it is doing. It would, however, be a little more efficient when run because the overhead involved in making large numbers of method calls has gone. It is a matter of judgement when to separate out a piece of code into another method. If doing so enables you to re-use the code in the method by calling that method more than once, it's generally a good idea, which will save you time when writing the code or if you ever have to make changes to it. Otherwise, it is a matter of balancing understandibility with efficiency. As you get more used to Java you may feel more at ease writing code with more complex loops within loops, as the second form of sort above. However, experts suggest that a good rule of thumb is that a single method should never be so long that it can't be viewed completely in one go on the computer screen. If your method becomes that long it would be a good idea to consider breaking it down by putting some of the code into subsidiary helper methods.

Sorting In Place in Java

The algorithm given is a sorting in place algorithm, that is it actually changes the elements of the array around in the place where they are, the initial array. Another name for this is destructive, because it destroys the original ordering of the array. By contrast, a constructive sort creates a new array to hold the sorted integers while leaving the old array unchanged.

The method sort had return type void, but the array the variable passed to it as an argument referred to was changed. To consider how this works, remember if a and b are of object types (anything except the primitive types, including all arrays even if the contents of the array are of a primitive type), then the assignment a=b doesn't make a copy of what b refers to and make a refer to that, rather it makes a refer to the same object that b refers to. So if you change the object a refers to, the object b refers to is also changed, and so on, because they are the same thing. This can be shown diagramatically with the variables having pointers to the object:

If a and b happen to be of some array type, then a=b will mean a and b are two different names for the same array, so: 

int[] a, b;
some code which sets b to refer to an array object
a=b;
will result in the following situation:

where the numbers are given just as an illustration of what could be in the array object. Note that the arrows here, representing variables referring to an object, should be considered as pointing to the whole array object, not to the particular cell where the arrow head happens to be. Java (unlike C) doesn't have the concept of a variable referring to a particular part of an array.

Assuming the numbers as in the diagram above, then executing 

a[2]=1;
will cause the situation to change to:

In other words, b[2] is changed to 1 as well as a[2] because a and b are two names for the same array object, so a[2] and b[2] are exactly the same thing (the same store location, not two separate store locations that both happen to hold 6).

When in the main method above we make the call 

sort(array);
a similar sort of thing happens. The effect when we start executing the call is as if we executed a=array (remember a is the parameter name in the method sort), except that array is a name used in the main method, and a a name used in the sort method. However, they refer to the same array, so using our previous example, we have:

So when the code for method sort changes a[i] for some i, the value of array[i] for that same i is changed, because they are the same thing.

Note that while the change in the value of an array in a method passes through to the code that called that method, the change in the value of a primitive won't. Suppose we have a method written: 

private static void swapvals(int m, int n)
{
 int temp;
 temp=n;
 n=m;
 m=temp;
}
You may be tempted to think that the code: 
int u,v;
u=5;
v=8;
System.out.println(u+" "+v);
swapvals(u,v);
System.out.println(u+" "+v);
will cause 
5 8
8 5
to be printed, because swapvals(u,v) would swap round the values in u and v. Actually, it won't. This is because if a and b are variables of primitive type (such as int), then a=b causes the value that is in variable b to be copied into variable a, but no connection between a and b is established:

So when swapvals(u,v) is called, it as as if: 

m=u;
n=v;
is executed before the code for swapvals is executed. This will result in the situation:

When this is followed by the code in method swapvals it results in the situation:

So the values in u and v are unaffected.

Executing the code: 

int m,n;
m=5;
n=8;
System.out.println(m+" "+n);
swapvals(m,n);
System.out.println(m+" "+n);
makes no difference, as the variables names m and n inside the execution of swapvals are different variables (albeit with the same names) from the variables outside. The situation at the end of the code for swapvals is:

Then when swapvals finishes executing, its local variables disappear, and we go back to the old set of variables where m still holds value 5 and n still holds value 8.

Matthew Huntbach

Last modified: 22 January 2004