Sorting

home1 home2
 Bib
 Algorithms
 Bioinfo
 FP
 Logic
 MML
 Prog.Lang
and the
 Book

Algorithms
 glossary
 Sorting
  Insertion
  Quick
  Merge
  Heap
  Dutch N.F.
  Radix

Selection Sort

Selection sort maintains a growing `front' section of the array which is (i)sorted and (ii)less than the remainder of the array. At each step, the smallest element in the `remainder' is selected and moved to enlarge the `front' section.

selection(int a[], int N)  /* in C */
/* sort a[1..N],  NB. 1 to N */
 { int i, j, smallest, aSmallest, temp;

   for(i=1; i < N; i++)
    { /* invariant: a[1..i-1] sorted
                and elements a[1..i-1] <= a[i..N] */

      smallest = i; /* find smallest in a[i..N] */
      aSmallest = a[i];

      for(j=i+1; j <= N; j++)
      /* a[smallest] is the least element in a[i..j-1] */
         if(a[j] < aSmallest)
          { smallest=j; aSmallest=a[j]; }
      /* a[smallest] is the least element in a[i..j] */

      temp=a[i]; a[i]=a[smallest]; a[smallest]=temp; /*swap*/
      /* a[1..i] sorted and elements a[1..i] <= a[i+1..N] */
    }

   /* a[1..N-1] sorted and elements a[1..N-1] <= a[N] */
   /* i.e. a[1..N] sorted. */
 }/*selection*/

At some intermediate stage, a[1..i-1] is sorted and, on an element by element basis, less than everything in a[i..N]. Find the smallest element remaining in a[i..N]:


             select
             smallest
             -------
a:  1  2  3  6  5  4
    -------  ^
    sorted   |
    & small  |
             i

Do this by examining a[i], a[i+1], ..., a[N]:


a:  1  2  3  6  5  4
             ^     ^
             |     |
             i     smallest

Swap a[i] with a[smallest]:


a:  1  2  3  4  5  6
    ----------
    sorted   ^
    & small  |
             |
             i

Now a[1..i] is sorted and less than everything remaining in a[i+1..N]. (Coincidentally a[1..N] happens to be sorted in this example.) Repeat until i=N-1.

Selection Sort Demonstration

Try other example input in the HTML FORM below, press `go' and experiment.

L
.
A
l
l
i
s
o
n
input:  
output:
trace:  

Complexity

Time

The number of comparisons of elements is

  (N-1) + (N-2) + ... + 1
= (N-1)*N/2
i.e. O(N2).

Space

The space-complexity is O(1), just a few scalar variables. NB. We do not count the size of the array being sorted because that is given, not created specifically for this algorithm.

Stability

Selection sort is not stable, the is the relative order of equal keys is sometimes changed. It is the swap that can do it, consider [2a,2b,1]. (Thanks to Giri Narasimhan 6/4/'05.)

Testing

Test sort programs on a few special cases:

  • the empty array!
  • an array of a single element,
  • an array of a small number of elements,
  • some already sorted data,
  • some reverse sorted data,
  • some random data (several sets),
  • data with duplicate keys.

Notes

  • Depending on your language, you may find yourself sorting a[1..N] or a[0..N-1]; watch those indices!


L. A. © Dept. Computer Science, University of W.A. 1984.
Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite
The GIMP
~ free photoshop
Firefox
web browser

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Friday, 29-Mar-2024 13:24:53 AEDT.