Sorting things out with Selection
December 4, 2010 Leave a comment
Not long after you’ve been introduced to writing programs would a typical programming instructor teach you how to sort a list of elements. Despite our stated (or, is it unstated) aversion to the instructional approach generally employed, let us go ahead and expound a bit on sorting.
You are given an array of n elements. We assume that we know how to compare any two elements of the array with one another (in other words, you wouldn’t be asked to compare apples and oranges). Let us assume that the array is one of n integers. We wish to sort the elements such that the smallest element occurs first, followed by successively larger elements.
1. Selection Sort
As the name suggests, we sort by performing some “selection”.
Take an arbitrary array of 5 elements – 23, 11, 54, 34, 27.
Now, we know that the sorted order is: 11, 23, 27, 34, 54.
As is clearly seen, 11 is the minimum element in this array, and occurs first in the sorted list. If we remove this 11 from the array, we find that 23 is the minimum element from among the ones remaining. Hence, 23 occurs in the sorted list just after 11. Similarly, on removing 23 also from the array, we find that 27 is the minimum from among the remaining elements, and unsurprisingly, occurs right after 23 in the sorted order.
So, we can see our modus operandi — Select (and remove) the minimum element in the array, and add it to the sorted list.
We’ll digress here for a bit to figure out how exactly we find the minimum element in an array.
Let’s take the following array — 23, 54, 15, 11, 46. We know that the 4th element of the array – 11 is the minimum.
Let’s assume that we read the elements of the array one by one from left to right.
We begin by reading 23. Since it is the only element that we have read so far, and we have no other element to compare it with, 23 is the least element we have encountered thus far. So, our current minimum is 23.
We next read 54. We compare it with the current minimum, which is 23. Now, 54 >23, and hence, the minimum encountered thus far remains 23.
Now, we come across 15. We compare it with the current minimum (23) and find that, voila, 15 is smaller than 23, and hence, 15 is smaller than any element we have encountered so far. So, we naturally set our current minimum to 15, and proceed.
We next read 11, and compare it with the current minimum (which is 15). Now, 11 < 15, and so, we set the current minimum to 11.
We proceed to read the next element, which is 46, and compare it with our current minimum (11). Since, 46 > 11, we let 11 remain as the minimum element encountered thus far.
We now realize that we have run out of elements in the array. Hence, the minimum element encountered thus far, 11, is also the minimum element of the array.
Let us look at pseudo-code for computing the minimum in an array of n elements. This should be simple enough to understand.
Input: Array A having n elements: A, A, …., A[n].
Output: The index of the minimum element in A.
min_index 1. (Comment: min_index (the index of the least element encountered so far) is a variable, initialized to 1.)
For index i going from 2 till n:
If ( A[i} < A[min_index])
then, min_index i.
For those familiar with the big-O notation, it should be clear that this procedure for finding the minimum in an n-element array takes O(n) steps.
Let’s say that our function for finding the minimum index, Find_Min_Index takes 3 arguments – an array, a starting index, and an ending index.
eg. The function call Find_Min_Index(Z, 4, 9) will find find the index of minimum element from among Z, Z,…, Z.
Now, back to sorting by successive selection of minimum elements.
From what we’ve seen so far, we can write a procedure for sorting an n-element array.
Input: Array A of n elements: A, A, …, A[n].
Output: A re-ordering of the elements of A such that the elements are sorted in increasing (or, to be more precise, non-decreasing) order.
For i going from 1 to n
index Find_Min_Index (A, i, n)
Swap A[i] and A[index].
That wasn’t very difficult. Again, for those familiar with asymptotic notation, the selection sort algorithm takes time. (It is easy to see why —- The first element of the sorted array is obtained by finding the minimum element from among n elements. This takes kn time (where, k is some constant). Similarly, the 2nd element of the sorted array is obtained by finding the minimum element from among n-1 elements. This takes k(n-1) time. Proceeding in the same manner, we find that the time needed to sort the array is .)