Data Structures & Algorithms In Go/

...

/

Selection Sort

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

Press + to interact
Go (1.6.2)
package main
import ("fmt")
func SelectionSort(arr []int) { 
  size := len(arr)
    var i, j, max int
    for i = 0; i < size; i++ {
        max = 0
        for 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 Code
func 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.

...