The following Go program implements the selection sort algorithm, which is a simple and intuitive sorting technique. It works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the array and moving it to the sorted portion.

Go Program

package main

import "fmt"

// selectionSort sorts an array using the selection sort algorithm.
func selectionSort(arr []int) {
    n := len(arr)
    
    // Traverse through all array elements
    for i := 0; i < n-1; i++ {
        // Find the minimum element in the remaining unsorted array
        minIndex := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        // Swap the found minimum element with the first element
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

func main() {
    // Sample array to be sorted
    arr := []int{64, 25, 12, 22, 11}
    
    fmt.Println("Original array:", arr)
    selectionSort(arr)
    fmt.Println("Sorted array:", arr)
}
    

Program Structure

The program consists of the following key components:

• Package Declaration: The program starts with the declaration of the main package, which is the entry point of a Go application.
• Import Statement: The fmt package is imported to enable formatted I/O operations.
• Selection Sort Function: The selectionSort function takes an array of integers as input and sorts it in place. It iterates through the array, finds the minimum element in the unsorted portion, and swaps it with the first unsorted element.
• Main Function: The main function initializes a sample array, prints the original array, calls the selectionSort function to sort the array, and finally prints the sorted array.

How Selection Sort Works

Selection sort divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items. Initially, the sorted sublist is empty, and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest) element from the unsorted sublist, swapping it with the leftmost unsorted element, and moving the boundary between the sorted and unsorted sublists one element to the right.

Time Complexity

The time complexity of selection sort is O(n²), where n is the number of items being sorted. This is because there are two nested loops: one for iterating through the array and another for finding the minimum element.

Conclusion

Selection sort is easy to understand and implement, but it is not efficient for large datasets compared to more advanced algorithms like quicksort or mergesort. However, it is a good educational tool for understanding the fundamentals of sorting algorithms.