top of page

Selection Sort

Tutoring > Data Structures > Selection Sort

In every case, selection sort has an O(n^2) or O(n squared) time complexity class. It is very similar to insertion sort.

Find the minimum.

The way selection sort works is it searches through the input array​ and finds the minimum value.

Then it puts this minimum value into a first position in the array which will end up being sorted in ascending order once all elements have been replaced.

 

  • We start with this array : {3, 5, 1, 4, 7, 6}

 

  • Scan the array to find the smallest.

   |3   5   1   4   7   6

^

  • 1 is the smallest so swap 1 with 3 which is the current first element.

    1 | 5   3   4   7   6

 

  • Scan the remaining array (to the right of the |) to find the smallest again.

     1 | 5   3   4   7   6

^

  • Now 3 is the smallest so we swap 3 with the second element in the array.

     1   3 | 5   4   7   6

 

  • Continue like this until all elements have been placed. Here is the full procedure:

   |3   5   1   4   7  6

    1 | 5   3   4   7   6

    1   3 | 5   4   7   6

    1   3   4 | 5   7   6

    1   3   4   5 | 7   6

    1   3   4   5   6 | 7

 

The lines where the smallest is the leftmost element to the right of the | we don't do anything, just move on to the next line, as this element is already in place.

bottom of page