Selection Sort

Selection Sort is a simple and intuitive sorting algorithm, particularly suitable for beginners to understand the basic concepts of sorting. It works by repeatedly finding the minimum element from the unsorted part of the array and placing it at the end of the sorted part. This article explains the principle and steps of Selection Sort in detail, providing a C code example to help beginners get started quickly.

Principle

The core idea of Selection Sort is:

Find the minimum (or maximum) element in the unsorted part of the array.
Swap this minimum element with the first element of the unsorted part.
Move the boundary of the sorted part one position to the right, shrinking the unsorted part.
Repeat the above steps until the entire array is sorted.

Its time complexity is O(n²), where n is the length of the array. Although it is less efficient in practice than Quick Sort or Merge Sort, its simplicity makes it an ideal starting point for learning algorithms.

Steps

Assuming we want to sort an integer array in ascending order, here are the detailed steps for Selection Sort:

Initialization: Start from the first element of the array, assuming it is the minimum in the unsorted part.
Find Minimum: Traverse the unsorted part to find the index of the minimum element.
Swap: Swap the found minimum element with the first element of the unsorted part.
Update Range: Move the boundary of the sorted part one position to the right (i.e., increment the starting position of the unsorted part).
Repeat: Repeat steps 2-4 for the remaining unsorted part until the entire array is sorted.

Implementation

Here is the C implementation of Selection Sort, with detailed comments to aid understanding.

main.c
#include <stdio.h>

// Selection Sort function
void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;
    
    // Outer loop: controls the starting position of the unsorted part
    for (i = 0; i < n-1; i++) {
        // Assume the first element of the unsorted part is the minimum
        min_idx = i;
        
        // Inner loop: finds the minimum element in the unsorted part
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j; // Update the index of the minimum element
            }
        }
        
        // Swap the minimum element with the first element of the unsorted part
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

// Helper function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Main function to test selection sort
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: ");
    printArray(arr, n);
    
    selectionSort(arr, n);
    
    printf("Sorted array: ");
    printArray(arr, n);
    
    return 0;
}

Compile & Run
$ gcc -o bin/selection-sort main.c
$ bin/selection-sort 
Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90 
$ 

Here is the Go implementation of Selection Sort, with detailed comments to aid understanding.

main.go
package main

import "fmt"

// selectionSort implements the selection sort algorithm
func selectionSort(arr []int) {
    n := len(arr)
    
    // Outer loop: controls the starting position of the unsorted part
    for i := 0; i < n-1; i++ {
        // Assume the first element of the unsorted part is the minimum
        minIdx := i
        
        // Inner loop: finds the minimum element in the unsorted part
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j // Update the index of the minimum element
            }
        }
        
        // Swap the minimum element with the first element of the unsorted part
        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
}

// printArray prints the elements of an array
func printArray(arr []int) {
    for _, val := range arr {
        fmt.Printf("%d ", val)
    }
    fmt.Println()
}

func main() {
    // Example array
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    
    fmt.Print("Original array: ");
    printArray(arr)
    
    selectionSort(arr)
    
    fmt.Print("Sorted array: ");
    printArray(arr)
}

$ gsk build -v
create selection-sort/bin/selection-sort-linux-amd64
$ ./bin/selection-sort-linux-amd64 
Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90

Summary

The core of Selection Sort is to find the minimum or maximum value from the unsorted part and place it at the end of the sorted part to achieve sorting.

Copyright Notice: Freely reproduced, non-commercial, no derivatives, attribution, and keep the source.

Author: afxcn

Source: https://gostartkit.com/docs/algo/selection-sort

Date Published: June 28, 2025

Principle​

Steps​

Implementation​

Summary​

Principle

Steps

Implementation

Summary