Learn

Selection sort is an in-place comparison sorting algorithm. It gets its name by selecting the smallest item that hasn’t been sorted yet and then implements the sort by finding the correct place to put it. It works by dividing the given input array into two virtual sub-lists. The first sub-list contains every element we’ve already sorted. The second sub-list, contains the elements that haven’t been sorted yet. This is the sub-list that we’ll be selecting the smallest item from.

Here is the logic of the selection sort algorithm we are going to build. Please expand the narrative window to view pseudocode — it’s a bit hard to parse the indentation level otherwise:

selectionSort(array)
 repeat (size - 1) times
  start at the beginning index of the unsorted sub-list as the current minimum
    walk through all elements of the unsorted sub-list to find the index of the smallest element and set as current minimum
  swap that element with the first element in the unsorted sub-list. That element is now part of the sorted sublist
end selectionSort

Initially, the sorted sub-list is empty and the unsorted sublist contains all the items.

Input array: [2, 7, -7, 20, -5]
Sorted sub-list: empty
Unsorted sub-list: 2, 7, -7, 20, -5

Selection sort works by taking the smallest item in an unsorted sub-list and swaps it with the first unsorted position, making it part of the sorted sub-list.

We have to repeat the process of selecting the smallest item in the unsorted sub-list and moving it into the sorted sub-list once for every item in the unsorted sub-list.

The algorithm will be implemented with two loops. The first loop will run size - 1 times because we have to do the process of selecting the smallest item in the list and moving it into the sorted sublist once for every item in the list. We have a -1 here because we don’t have to do this for the very last item. If every other item in the list has been sorted, the last item is guaranteed to be sorted as well!

We will store the first position in the unsorted sub-list as our current minimum.

Input array: [2, 7, -7, 20, -5]
Sorted sub-list: empty
Unsorted sub-list: 2, 7, -7, 20, -5
Current minimum: 2

The inner for loop will iterate through the unsorted sub-list n times making comparisons to find the smallest value in the unsorted sub-list.

For each comparison of current minimum to the remaining items in the unsorted sub-list, the algorithm will check :

If the unsorted number in comparison is less than our current minimum. If it is not, we keep going.

Unsorted sub-list 2, 7, -7, 20, -5
Current minimum: 2
Next unsorted element: 7 // Current minimum does not change

If a smaller number is found, set the index as the new current minimum and continue to the end of the array.

Unsorted sub-list: 2, 7, -7, 20, -5
Current minimum: 2
Next unsorted element: -7 // Current minimum is -7

Unsorted sub-list: 2, 7, -7, 20, -5
Current minimum: -7
Next unsorted element: 20 // Current minimum does not change

Unsorted sub-list: 2, 7, -7, 20, -5
Current minimum: -7
Next unsorted element: -5 // Current minimum does not change

When we reach the end of comparisons in the unsorted sub-list the smallest element is selected and swapped with the first unsorted position, and that element is now considered a part of the sorted sub-list.

Original input array: [2, 7, -7, 20, -5]
2 swaps places with -7
After swap: [-7, 7, 2 20, -5]

We can consider -7 to be a part of the sorted sub-list and 2 to be a part of the unsorted sub-list.

We’ll have to keep track of where the boundary between our unsorted sub-list and sorted sub-list is. Now that we’ve sorted one element, that boundary has moved to the right by one giving us a new current minimum.

Unsorted sub-list: 7, 2, 20, -5
Current minimum: 7

We would then find the next minimum element -5 and swap it to the new start of the unordered list.

Original input array: [2, 7, -7, 20, -5]
-5 swaps places with 7
After two swaps: [-7, -5, 2 20, 7]

We will repeat the process until we have reached the last element in our input array which we will consider to be sorted by the time we have reached it.

Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?