Sorting brings up the concept of an algorithm. An algorithm is a method of solving a problem. In the case of sorting there are many different algorithms. Some are quicker than others, so that the overall number of steps required to sort a collection varies depending on the algorithm used. Obviously, it's better to use a quick algorithm, but we shall leave detailed efficiency analysis of algorithms to the Introduction to Algorithms course, which will discuss several further sort algorithms.
The sorting algorithm we discuss here, called selection sort, is certainly not amongst the most efficient, so it is not one you should use if you are writing a program to do any serious sorting. It's given as the one which is perhaps the simplest to understand. Suppose you go through the array looking for the position of the smallest number in it. When you have found it you swap it with the number in the first position in the array. Next you go through all the array except the first element, which you know now holds the smallest number, looking for the next smallest number. You swap that number with the number in the second position in the array. Next you go through all the array except the first two elements (which you know hold the smallest two numbers in order) looking for the third smallest number, and so on. You will put the third, fourth, fifth and so on smallest numbers in the appropriate place, and if you carry on doing this you will eventually have sorted the array.
Here's a program which reads an array and sorts it:
1 import java.io.*;
2
3 class Numbers4
4 {
5 // Read a number of integers and store them in an array.
6 // Sort the numbers in place.
7
8 static final int SENTINEL = -999;
9 static final int MAXNUMS = 100;
10
11 public static void main (String[] args) throws IOException
12 {
13 int [] data;
14 int count,n;
15 BufferedReader in = Text.open(System.in);
16 data = new int[MAXNUMS];
17 for(count=0; ;count++)
18 {
19 System.out.print("Enter number "+(count+1)+" (or ");
20 System.out.print(SENTINEL+" to finish): ");
21 n=Text.readInt(in);
22 if(n==SENTINEL)
23 break;
24 data[count]=n;
25 }
26 System.out.println("The numbers entered were:");
27 NumberOps.printall(data,count);
28 Sorter.sort(data,count);
29 System.out.println("After sorting the number are:");
30 NumberOps.printall(data,count);
31 }
32 }
As previously, a sentinel value must be typed in to indicate the end of
the numbers, and since we don't know how many numbers there will be in
advance, we have to create an array of the maximum size we might need.
This program re-uses the printall method we introduced
previously, kept in class NumberOps. The sorting method is
kept in a separate class called Sorter, so from the point of
view of the class Numbers4 above, the actual algorithm used
for sorting is unknown. All Numbers4 needs to know is that
calling Sorter.sort(data,count), as it does on line 28 causes
the numbers in array data to get sorted, with count
indicating how much of array data is actually to be treated as
data.
The fact that Numbers4 doesn't need to know how Sorter
sorts numbers is good. As mentioned above, the algorithm we shall look at
is inefficient. But if it's left entirely in class Sorter,
if we get round to changing it to something more efficient, we can change
the sort method in Sorter without having to make
any changes to Numbers4. In fact we don't even have to
recompile Numbers4: if sort in Sorter
is changed, next time Numbers4 is run it will automatically make
use of the new version of sort.
So here is the initial version of Sorter:
1 class Sorter
2 {
3
4 public static void sort(int [] a,int n)
5 // sort (in place) the first n integers in array a
6 // uses selection sort
7 {
8 int sorted,minPos;
9 for(sorted=0;sorted<n;sorted++)
10 {
11 minPos=indexSmallest(a,sorted,n);
12 swap(a,sorted,minPos);
13 }
14 }
15
16 public static void swap(int [] a,int pos1,int pos2)
17 // swap the integers at index pos1 and pos2 in array a
18 {
19 int temp;
20 temp=a[pos1];
21 a[pos1]=a[pos2];
22 a[pos2]=temp;
23 }
24
25 private static int indexSmallest(int [] a,int pos1,int pos2)
26 // Return the index of the smallest integer in the portion
27 // of array a starting at index pos1 and up to but not
28 // including index pos2.
29 {
30 int i,pos=pos1;
31 for(i=pos1+1; i<pos2; i++)
32 if(a[i]<a[pos])
33 pos=i;
34 return pos;
35 }
36
37 }
As you can see, the method sort makes use of two further methods
in Sorter: swap and indexSmallest.
Note that inside Sorter, where they are called on lines 11 and
12, these do not have to be referred to as Sorter.swap and
Sorter.indexSmallest. In general, a class may use its own methods
without having to prefix them with the class name. To demonstrate a little
more Java, method indexSmallest has been made private
rather than public - shown by the first word of its header on
line 25. What this means is that method indexSmallest may
only be used inside Sorter, it is simply a helper
method for other methods in side Sorter. Any attempt to try and
use Sorter's indexSmallest outside
Sorter, by having a call Sorter.indexSmallest
would result in the same error message you would get if you attempted to
use a method that did not exist inside Sorter.
You should be able to see how the algorithm for selection sort described
above translates to a Java program. The method indexSmallest
returns the index of the smallest number in a section of the array it takes
as an argument between two positions it also takes as arguments. The loop
in sort over lines 9-13 is the one that looks for the
smallest element and swaps it with the first element (indexed by 0), then
looks for the smallest element in all but the first element of the array
(i.e. in the section starting with index 1) and swaps it with the second
element (i.e. the one indexed by 1). The variable sorted
increases by 1 each time round this loop, marking the current position in
the array where sorting has reached.
The method indexSmallest is very similar to the method we saw
earlier for finding the index of the smallest element in an array. It
restricts itself to the portion of the array between its arguments
pos1 and pos2, including the element indexed by
pos1 up to but not including the one indexed by pos2.
The method swap needs to have a temporary variable. Line 20
copies the contents of a[pos1] into this temporary variable.
Line 21 copies the contents of a[pos2] into a[pos1].
This overwrites and thus detroys the old contents of a[pos1],
but we saved a copy of them in the temporary variable. In line 22 this copy
is copied into a[pos2] overwriting the original value of
a[pos2]. So it can be seen the overall effect is to swap the
contents of a[pos1] and a[pos2], where
a is the array passed as an argument, and the two indexes
pos1 and pos2 are also passed as arguments.
System.out.print("Enter an integer: ");
n=Text.readInt(in);
SillyMethods.square(n);
System.out.println("After squaring the integer is: "+n);
with the following method in the class SillyMethods:
public static void square(int m)
{
m=m*m;
}
what would happen? If you typed 3 in response to the prompt,
you would find the following being printed:
After squaring the integer is: 3The
square method given is useless because all that
happens is that the 3 is copied into the variable
m which is local to square, that value is
squared and copied back to m, but it is then lost as the
execution of method square finishes and its local variables
disappear. It wouldn't work if you happened to use the same name n
for the local variable in square as you used for the initial
integer:
public static void square(int n)
{
n=n*n;
}
because the local variable called n in square is
a different variable (albeit one with the same name) from the one in the
method that called it.
If you want to change the contents of an integer variable through a method, you can only do so by returning a value from that method and assigning that value to the variable, as in:
System.out.print("Enter an integer: ");
n=Text.readInt(in);
n=SensibleMethods.square(n);
System.out.println("After squaring the integer is: "+n);
where the method is defined in class SensibleMethods as:
public static int square(int m)
{
m=m*m;
return m;
}
What happens here is that the contents of n are copied into
local variable m, the contents of local variable m
are changed within square, and returned to the calling
method as the value of the expression SensibleMethods.square(n),
and the assignment there copies the returned value into variable n.
So what are we to make of line 28 in Numbers4 above:
Sorter.sort(data,count);
Surely by the same argument, any change made to the array data
passed to method sort in class Sorter would really
only be made to the contents of local array variable a within
the method sort.
The explanation for the discrepancy is that in Java assignment is copying
only for the primitive types - numbers, booleans and characters.
Everything else in Java is an object, and assignment of one object
variable to another is actually a form of aliasing: giving a second
name to the object. So, if a and b are integer
variables in Java, executing a=b means the content of
a is copied into b But if they are object variables,
executing a=b means b becomes another name for the
same object as that referred to by a. For those who are
familiar with the concept of "pointers" in other languages, when a
and b are object variables, they actually hold pointers to
objects, so assignment is pointer copying. For those unfamiliar with pointers,
do not worry about this: Java was designed as a language which hides the
complexity of directly handling pointers.
So when the call Sorter.sort(data,count) is made on line 28 of
Numbers4, the effect is as if there were an assignment
a=data to the local variable a for the
sort method of Sorter (and also n=count to
the local variable n). Arrays are a form of object, so the
assignment a=data does not, as you might imagine, copy all the
integers in data to a, rather it makes a
a name for the same array inside method sort. Therefore
any changes to items stored in the array a change data
since they are the same thing. So when sort moves the integers
in the array around to put them in sorted order, that change is retained
when sort has finished and execution goes on after line 28
of Numbers4.
The following program demonstrates that array assignment is in fact aliasing:
1 import java.io.*;
2
3 class Numbers5
4 {
5 // A demonstration that array assignment is aliasing
6
7 static final int SENTINEL = -999;
8 static final int MAXNUMS = 100;
9
10 public static void main (String[] args) throws IOException
11 {
12 int [] a;
13 int [] b;
14 int count,n;
15 int pos1, pos2;
16 BufferedReader in = Text.open(System.in);
17 a = new int[MAXNUMS];
18 for(count=0; ;count++)
19 {
20 System.out.print("Enter number "+(count+1)+" (or ");
21 System.out.print(SENTINEL+" to finish): ");
22 n=Text.readInt(in);
23 if(n==SENTINEL)
24 break;
25 a[count]=n;
26 }
27
28 System.out.println("The numbers entered into array a are:");
29 NumberOps.printall(a,count);
30
31 System.out.println("Do array assignment b=a");
32 b=a;
33 System.out.println("The numbers held in b are:");
34 NumberOps.printall(b,count);
35
36 System.out.println("Enter two positions to swap in array a:");
37 System.out.print("Position 1: ");
38 pos1=Text.readInt(in);
39 System.out.print("Position 2: ");
40 pos2=Text.readInt(in);
41 Sorter.swap(a,pos1-1,pos2-1);
42 System.out.println("After the swap, the numbers in a are:");
43 NumberOps.printall(a,count);
44 System.out.println("And the numbers in b are:");
45 NumberOps.printall(b,count);
46 }
47 }
It works as Numbers4, reading a sequence of integers terminated
by a sentinel into an array. On line 32 it does an assignment of that
array a to b. Line 34 shows that when
the contents of b are printed they are the same as those
of a, but, of course, this does not tell us whether they
are copies or actually the same data. Lines 36-45 demonstrate that
a and b are actually the same thing. The user
is invited to call the swap method to swap over two numbers
in array a. When this is done the contents of a
and b are printed out and it will be seen that the numbers
have been swapped in b as well, hardly surprising once you
realise that the assignment a=b on line 32 means that
at this point b is a.
In the real world, we frequently have more than one name for the same entity. If in 1998 an assassin stabbed the Prime Minister of the UK, we would not be surprised to hear that at precisely the same time the Prime Minister started to bleed, Tony Blair started to bleed. "The Prime Minister of the UK" and "Tony Blair" are two names for the same person. You might variously refer to one individual as "The lecturer for Introduction to Programming", "the man standing over there", "Matthew Huntbach", "Peter Huntbach's brother", and so on. In computer programming, as in real life, aliasing can cause problems if you don't realise that two things you think are different because they have different names are in fact the same thing. The person who swore at a driver who blocked his way on the way to be interviewed, only to find the person he swore at on the other side of the table when he entered the interview room half an hour later, is a victim of a real world aliasing problem. He did not realise "that fool who is blocking my way" was an alias for "the person who is going to interview me".
Note that the == test for objects is actually a test for aliasing.
If a and b are variables of some object type, then
only if a is an alias for b will a==b
evaluate to true. Otherwise, it will evaluate to
false even if a and b hold the same
information. So == is a test for equality of value (rather than
equality of reference) only when it is used with primitive types. Note that
Strings are not a primitive type - they are objects as well.
Numbers5 above by changing line 32 to:
b=(int[])a.clone();(it might be a good idea to change line 31 appropriately as well). Some objects, including arrays, have the ability to produce a copy, obtained in a program adding the suffix
.clone() to their name. Note that the
type of the copy has to be explicitly specified by type casting. In this case
the type is "array of integers", in Java that is int[], hence the
a.clone().
However, rather than making a copy and then using a destructive method to alter the copy, we might prefer a method which takes the original as its argument, but constructs and returns a new object which is like a copy of the original with the desired changes made. Such a method is termed constructive or non-mutating. Here is a program which demonstrates the use of a constructive form of sort method:
1 class Numbers6
2 {
3 // A demonstration of non-mutating sort of an array of integers
4
5 static final int SENTINEL = -999;
6 static final int MAXNUMS = 100;
7
8 public static void main (String[] args) throws IOException
9 {
10 int [] data;
11 int [] sortedData;
12 int count,n;
13 BufferedReader in = Text.open(System.in);
14 data = new int[MAXNUMS];
15 for(count=0; ;count++)
16 {
17 System.out.print("Enter number "+(count+1)+" (or ");
18 System.out.print(SENTINEL+" to finish): ");
19 n=Text.readInt(in);
20 if(n==SENTINEL)
21 break;
22 data[count]=n;
23 }
24 System.out.println("The numbers entered were:");
25 NumberOps.printall(data,count);
26 sortedData=Sorter.makeSort(data,count);
27 System.out.println("After sorting the number are:");
28 NumberOps.printall(sortedData,count);
29 System.out.println("To show the old data is unchanged, here it is:");
30 NumberOps.printall(data,count);
31 }
32 }
The constructive version of sort here is called
makeSort. Code for makeSort could just
use clone to copy the input array, then call the destructive
sort to sort it. So the following would be put into class
Sorter to give it a constructive sort method:
public static int[] makeSort(int [] a,int n)
{
int [] b = (int[])a.clone();
sort(b,n);
return b;
}
However, in the Sorter.java file in the
/import/teaching/BSc/1st/ItP/numbers directory, we have
taken the opportunity to show a sort method using a different algorithm,
insertion sort. Here is the method for it, plus a private method
which it uses:
1 public static int[] makeSort(int [] a,int n)
2 // return a new array which is the sort of the first n
3 // integers of array a
4 {
5 int i;
6 int [] b = new int[n];
7 for(i=0;i<n;i++)
8 insert(a[i],b,i);
9 return b;
10 }
11
12 private static void insert(int m,int [] a,int n)
13 // insert integer m in first n cells in ordered array a
14 {
15 int j;
16 for(j=n;j>0&&a[j-1]>m;j--)
17 a[j]=a[j-1];
18 a[j]=m;
19 }
How this makeSort works is to first create an array
of n integers, and then insert the integers from the input
array one at a time, each time inserting in the correct order. Line 6
creates the new array. Each time round the loop on lines 7-8 another
integer is inserted, using the private destructive method insert.
Each time round this loop, i holds the number of integers
that have been inserted so far. Being destructive, insert changes
the contents of the array b which is passed to it as an argument
(and just for demonstration is called a locally). Insertion in
the correct place is done by starting at the ith location in
the array (makeSort's i becomes
insert's n) and moving the integers already put
in the array up one place (done on line 17) until the correct insertion
point is found. The correct insertion point is either when all integers have
been moved up one place, so the new integer being inserted goes right at
the front in the location indexed by 0, or when the next integer looked at
in the array is less than the integer being inserted. Because the array is
looked at from the nth location first downwards, the control
variable j is reduced by 1 each time round the loop, which is
done by the j-- on line 16, rather than increased by one as
we have seen in for loop operations over arrays so far.
The loop in insert has two conditions linked by &&,
to cover the two conditions which cause execution to exit it.
The first, j>0, fails and hence causes exiting from the loop
when the beginning of the loop has been reached and the new integer is to
go in the array location indexed by 0, the second, a[j-1]>m,
fails when the integer being inserted, m, is no longer
less than the next integer being looked at in the array. Note in this
case the blocking effect of && is necessary. When the first
condition, a, of a&&b fails,
there is no need to evaluate the second condition b,
because in logic FALSE AND X is FALSE whatever the value of X.
Java, like C, follows this, so in a&&b, the
condition b is not evaluated if the condition
a evaluates to false. In this case, that
stops an ArrayOutOfBoundsException since the first condition
will fail when j is 0. If the second condition were evaluated
at this point, it would mean an attempt to access the non-existent location
a[-1]. Similarly, since TRUE OR X is TRUE for any X in logic,
in a||b, b is not
evaluated if a evaluates to true.
These notes were produced as part of the course Introduction to Programming as it was given in the Department of Computer Science at Queen Mary, University of London during the academic years 1998-2001.
Last modified: 18 Jan 2001