27

Selection Sort

Definition:

Selection sort is a type of sort algorithm that sort the unsorted arrays.

In worst, average and best case its time complexity is O(n^2) (n square). It is inefficient in large data sets. However, it has simple implementation and it does not require extra memory.

Its properties:

  • Not stable,
  • O(n^2) time complexity,
  • Not adaptive,
  • O (1) memory space,
  • In-place comparison sort,
  • O ( n) for swaps.

How does it work?

In selection sort, array is divided into 2 parts : sorted and unsorted list.

  1. Firstly, sorted list is empty, unsorted list has entire input.
  2. Find the smallest element in the unsorted list, and put it into sorted list.
  3. After all, array is sorted.

Example:

70  52  45  5   8  // initially
5  52  45  70  8 // sorted list= 5 
5  8  45  70 52 // sorted list= 5 8
5  8  45 70 52  // sorted list= 5 8 45 
5  8  45 52 70 // sorted list= 5 8 45 52 
5  8 45 52 70 // sorted list=  5 8 45 52 70

 

A figure below shows the selection sort:

Selection_sort_animation

Animated Selection Sort

Animation:

For better understanding, go to this animation page.

Pseudocode:

for i = 1:n,
    k = i
    for j = i+1:n, if a[j] < a[k], k = j
    → invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    → invariant: a[1..i] in final position
end

References:

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

http://www.sorting-algorithms.com/

Figure from:  http://en.wikipedia.org

 

For more algorithms, go to Algorithms Section.