Go – Selection Sort

In this tutorial, we will learn how to implement the Selection Sort algorithm using the Go programming language (Golang).

Selection Sort is a simple sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted portion of the list and places it in its correct position. We will provide a detailed explanation and an example program to implement Selection Sort.

Logic of Selection Sort

The Selection Sort algorithm involves the following steps:

  1. Divide the List: Divide the list into a sorted and an unsorted section. Initially, the sorted section is empty.
  2. Find the Minimum: Traverse the unsorted section to find the smallest element.
  3. Swap the Elements: Swap the smallest element with the first element in the unsorted section.
  4. Repeat: Move the boundary of the sorted section by one and repeat until the list is fully sorted.

Selection Sort has a time complexity of \( O(n^2) \), where \( n \) is the number of elements. It is not suitable for large datasets but is simple and intuitive for small ones.

Example Program for Selection Sort

Program – selection_sort.go

</>
Copy
package main

import "fmt"

// Function to implement Selection Sort
func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        // Find the index of the minimum element in the unsorted section
        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() {
    // Input array
    arr := []int{64, 25, 12, 22, 11}

    // Display the original array
    fmt.Println("Original array:", arr)

    // Sort the array using Selection Sort
    selectionSort(arr)

    // Display the sorted array
    fmt.Println("Sorted array:", arr)
}

Explanation of Program

  1. Function Definition: The selectionSort function accepts a slice of integers and sorts it in ascending order using the Selection Sort algorithm.
  2. Outer Loop: The outer loop iterates through the array, treating each element as the starting point of the unsorted section.
  3. Find the Minimum: The inner loop finds the index of the smallest element in the unsorted section by comparing elements.
  4. Swap Elements: The smallest element is swapped with the first element of the unsorted section using Go’s shorthand syntax arr[i], arr[minIndex] = arr[minIndex], arr[i].
  5. Display Results: The original and sorted arrays are displayed using fmt.Println.

Output

This program demonstrates the Selection Sort algorithm, which iteratively selects the smallest element and places it in its correct position until the list is fully sorted.