Iteration: Selection Sort 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
0)
{
str+=a[0];
for(int i=1; i 
