Selection Sort

Published on 02 December 2018 (Updated: 04 February 2024)
Selection Sort

Welcome to the Selection Sort page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.

This article was written by:

Description

Selection sort is an algorithm that operates on two lists, one of sorted elements and one of unsorted. With each pass, the algorithm finds the smallest item in the unsorted list and moves it to the front of the sorted list. At the beginning the sorted list is empty, and the algorithm completes when the unsorted list is empty (meaning that all elements have been moved to the sorted list).

There is also a variant that uses a single list and moves the elements in place. In this variant, the sorted elements are just placed at the front of the list rather than in a separate list, and the algorithm starts each pass with the index of the first unsorted element in the list.

Performance

The performance of sorting algorithms is generally defined in "Big O notation". If you are not familiar with such notations, please refer to the relevant article by Rob Bell or the Wikipedia entry listed in further readings below.

Cases Big O Notatation
Best case O(n2)
Average case O(n2)
Worst case O(n2)

Selection sort always performs at O(n2). This is because the algorithm's loops do not depend on the values of the items in the list. That means that even if the list is already sorted, the full sorting process will still be performed.

Examples: Two lists

In the examples below, each row is a single pass through all elements in the unsorted list. The element in bold is the one that will be moved to the sorted list after the pass.

"4, 5, 3, 1, 2"

Sorted List Unsorted List
  4 5 3 1 2
1 4 5 3 2
1 2 4 5 3
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5  

"3, 5, 4, 1, 2"

Sorted List Unsorted List
  3 5 4 1 2
1 3 5 4 2
1 2 3 5 4
1 2 3 5 4
1 2 3 4 5
1 2 3 4 5  

Examples: Single list

In the examples below, each row is a single pass through all elements in the unsorted list. The element in bold is the one that will be moved to the end of the sorted section after the pass.

"4, 5, 3, 1, 2"

"3, 5, 4, 1, 2"

Requirements

Write a sample program that takes a list of numbers in the format "4, 5, 3, 1, 2". It should then sort the numbers and output them:

$ ./selection-sort.lang "4, 5, 3, 1, 2"
1, 2, 3, 4, 5

The solution should handle duplicate elements

$ ./selection-sort.lang "4, 5, 3, 1, 4, 2"
1, 2, 3, 4, 4, 5

In addition, there should be some error handling for situations where the user doesn't supply correct input.

Testing

Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Selection Sort. In order to keep things simple, we split up the testing as follows:

Selection Sort Valid Tests

Description Input Output
Sample Input "4, 5, 3, 1, 2" "1, 2, 3, 4, 5"
Sample Input: With Duplicate "4, 5, 3, 1, 4, 2" "1, 2, 3, 4, 4, 5"
Sample Input: Already Sorted "1, 2, 3, 4, 5" "1, 2, 3, 4, 5"
Sample Input: Reverse Sorted "9, 8, 7, 6, 5, 4, 3, 2, 1" "1, 2, 3, 4, 5, 6, 7, 8, 9"

Selection Sort Invalid Tests

Description Input
No Input  
Empty Input ""
Invalid Input: Not A List "1"
Invalid Input: Wrong Format "4 5 3"

All of these tests should output the following:

Usage: please provide a list of at least two integers to sort in the format "1, 2, 3, 4, 5"

Articles