A Collection of Code Snippets in as Many Programming Languages as Possible
This project is maintained by TheRenegadeCoder
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.
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.
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.
Best case | O(n^{2}) |
Average case | O(n^{2}) |
Worst case | O(n^{2}) |
Selection sort always performs at O(n^{2}). 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.
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.
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 |
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 |
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.
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.
The following table contains various test cases that you can use to verify the correctness of your solution:
Description | Input | Output |
---|---|---|
No Input | Usage: please provide a list of at least two integers to sort in the format "1, 2, 3, 4, 5" | |
Empty Input | "" | Usage: please provide a list of at least two integers to sort in the format "1, 2, 3, 4, 5" |
Invalid Input: Not a list | 1 | Usage: please provide a list of at least two integers to sort in the format "1, 2, 3, 4, 5" |
Invalid Input: Wrong Format | 4 5 3 | Usage: please provide a list of at least two integers to sort in the format "1, 2, 3, 4, 5" |
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 |