Selection Sort

Home »  Selection Sort

Overview

A selection sort is a very simple sorting algorithm. The basic idea is that you start off with a data collection that has two portions.

  1. Sorted Portion
  2. Unsorted Portion

Initially you have an unsorted portion that is the size of your entire collection and a sorted portion of size “zero”. The goal of the sort is to move all of the unsorted data elements into the sorted portion. This is accomplished by checking each element in the unsorted portion to locate the smallest item. This item is then swapped with the first unsorted element. This swap causes the sorted section to grow by one element and the unsorted section to decrease by one element.

The visualization below shows this process. The animation includes a smallest box that indicates what element is the smallest item that has been located so far in the unsorted section. The checking box indicates what element is being evaluated against the smallest element (to determine if it is smaller). The array represents the sorted and unsorted sections. When an element has been turned green it is sorted. The highlighted/yellow element is the current smallest element. The red elements are unsorted.

Animation

Pseudo Code

locate position of the first unsorted element
search unsorted data and identify smallest element
swap first unsorted element with smallest element
repeat until size of unsorted data equals zero

That is it! Nothing more to it! It is a pretty simple sort and it is very efficient when it comes to space, but it is very inefficient when it comes to time.

Pros

  • Simple to understand.
  • Easy to implement.
  • Excellent space efficiency O(1).

Cons

  • Very slow/poor time efficiency O(n2)

Space Efficiency

The space efficiency of the algorithm is excellent. Outside of the memory that is required to store the unsorted data set, you only need enough memory to hold one additional object for the swap. For example,

  1. Copy the smallest element to the temporary memory space.
  2. Copy the first unsorted element to the location of the smallest element.
  3. Copy the element from the temporary memory space to the location of the first unsorted element

Time Efficiency

The time efficiency of the algorithm is poor. This is because the algorithm requires nested loops which yields an O(n2) efficiency. For example:
Outer loop to locate and update the current unsorted element
Inner loop to locate the smallest element