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.

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 Code:

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!
In addition to the original solution in the video tutorial, I added recursion solution here.

Actionable:
Download SelectionSort.java
Watch tutorial
The complete list of coding interview questions

Comments are closed