Golang Selection Sort Algorithm

1. Introduction

Selection Sort is a simple comparison-based sorting algorithm. The main idea behind this algorithm is to divide the input list into two parts: a sorted and an unsorted sublist. At each step, the algorithm finds the smallest (or largest, depending on the sorting order) element from the unsorted sublist and swaps it with the leftmost unsorted element, moving the boundary between the two lists one element to the right.

2. Implementation Steps

1. Start from the first element of the array as the minimum.

2. Traverse through the unsorted sublist to find the smallest element.

3. Swap the smallest element found with the first element of the unsorted sublist.

4. Move the boundary between the sorted and unsorted sublist one element to the right and repeat the process until the entire list is sorted.

3. Implementation in Golang

package main
import (
	"fmt"
)
func SelectionSort(arr []int) {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		minIdx := i
		for j := i + 1; j < n; j++ {
			if arr[j] < arr[minIdx] {
				minIdx = j
			}
		}
		// Swap the found minimum element with the first element
		arr[i], arr[minIdx] = arr[minIdx], arr[i]
	}
}
func main() {
	data := []int{64, 34, 25, 12, 22, 11, 90}
	fmt.Println("Original array:", data)
	SelectionSort(data)
	fmt.Println("Sorted array:  ", data)
}

Output:

Original array: [64 34 25 12 22 11 90]
Sorted array:   [11 12 22 25 34 64 90]

Explanation:

1. The SelectionSort function sorts an array using the selection sort algorithm.

2. For every index i in the array, it finds the minimum element in the unsorted sublist starting from index i.

3. Once the minimum element is found in the unsorted sublist, it is swapped with the element at index i.

4. The process continues, incrementing the starting index of the unsorted sublist until the entire array is sorted.

5. The main function initializes an array, displays its original state, sorts it using SelectionSort, and then displays the sorted state.

Though Selection Sort is conceptually simple and easy to implement, it is inefficient for larger lists with a time complexity of O(n^2). It performs many unnecessary comparisons even if a part of the array is sorted.