## Sorting

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

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

## 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.Allison
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 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 Monday, 25-Sep-2023 13:09:32 AEST.