Selection Sort
Let’s discuss the selection sort in depth.
We'll cover the following...
Introduction
The selection sort algorithm traverses an unsorted array and puts the largest value at the end of it. This process is repeated n-1 times. This algorithm also has a quadratic time complexity, but it performs better than both bubble sort and insertion sort as fewer swaps are required in this approach. The sorted array is created backward in selection sort.
Let’s look at an illustration of the selection sort to better understand how it works.
Code example
package mainimport ("fmt")func SelectionSort(arr []int) {size := len(arr)var i, j, max intfor i = 0; i < size; i++ {max = 0for j = 1; j < size-1-i; j++ {if arr[j] > arr[max] {max = j}}arr[size-1-i], arr[max] = arr[max], arr[size-1-i]}}//Testing Codefunc main() {data := []int{9, 1, 8, 2, 7, 3, 6, 4, 5}SelectionSort(data)fmt.Println(data)}
Analysis
-
The outer loop decides the number of times the inner loop will iterate. For an input of n elements, the outer loop will iterate n number of times.
-
The largest value is calculated in each iteration and placed at the end of the array after each inner loop iteration.
-
This is the final replacement of the maximum value to the proper location. The sorted array is created backwards.