Selection sort (2 solutions) – Code

Selection Sort is one of three well-known simple sorting algorithms (ie bubble sort, insertion sort and selection sort). It is intuitive. Starting from the first element of the array, find the smallest one in each iteration, and put it at the front.


selection sort

As other two simple sorting algorithms, we can use nested for loops in the iterative implementation. The outer loop iterates through the first to second to last element. The inner loop starts from the index of outer loop +1, and iterates through to the last one. at beginning, we initialize a variable min to the outer loop index, as the index of the smallest number. After completing the inner loop, the smallest value swap to the front.

Using the same logic, we can implement using recursion. At the beginning of recursion method, we initialize the min, and start the inner loop. After finishing, swap the value of smallest with the front. Then call itself for the next element.

Question: sort the number in an array in ascending order.

Java

JavaScript

Python

Doodle

selection sort doodle

Output:
original array:[19, 33, 4, 61, 5, 38, 36, 21, 0]
Iterative result:[0, 4, 5, 19, 21, 33, 36, 38, 61]

original array:[19, 33, 4, 61, 5, 38, -36, 21, 0]
Recursive result:[-36, 0, 4, 5, 19, 21, 33, 38, 61]

O notation:
Iteration:
Time Complexity: O(n^2)
Space complexity: O(1)
Recursion:
Time Complexity: O(n^2)
Space complexity: O(n)

Note:
If you have any questions or want to put comments, please post at youtube. I will answer you!


Download SelectionSort.java
Selection sort (YouTube)
Selection sort animated visual

Comments are closed