**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.

- Firstly, sorted list is empty, unsorted list has entire input.
- Find the smallest element in the unsorted list, and put it into sorted list.
- 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:

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 positionend

**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.