Selection Sort

Given an array of integers, your task is to sort the array in ascending order using the Selection Sort algorithm.

Selection Sort works by repeatedly selecting the smallest element from the unsorted portion of the array and moving it to the correct position in the sorted portion.

The algorithm is in-place and does not require extra space, but it is not the most efficient for large datasets.

Selection Sort is a comparison-based sorting algorithm. It builds the final sorted array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning of the sorted part.

How It Works

Imagine you're sorting cards on a table. You start from the left and look through all the remaining cards to find the smallest one. Once found, you swap it with the card you were initially pointing at. You then move one position to the right and repeat the process until all cards are sorted.

The same logic is applied in Selection Sort. At each step:

1. We assume the current position has the smallest value.
2. We scan through the remaining part of the array to find if there is a smaller number.
3. If we find one, we swap it with the current position. The value in the current position is sorted.
4. We repeat this until we reach the end of the array.

Case Analysis

• Normal Case: In an average unsorted array like [64, 25, 12, 22, 11], the algorithm will perform several swaps to sort the values step-by-step into ascending order.
• Already Sorted: If the array is already sorted, Selection Sort will still go through all comparisons but no swaps will be needed.
• Reverse Sorted: If the array is in descending order, the algorithm performs the maximum number of swaps, moving the smallest values from the back to the front.
• Single Element: If there's only one element, it's already sorted by default.
• Empty Array: There's nothing to sort, so the result is simply an empty array.
• All Elements Equal: Since all elements are the same, no swaps are needed, and the array remains unchanged.
• Mixed Values: The algorithm still works correctly with negative numbers, zero, and positive values. It always selects the smallest from the remaining section.

Why Use Selection Sort?

Selection Sort is a great algorithm for teaching and understanding sorting logic because of its simplicity. However, for very large arrays or when performance matters, faster algorithms like Merge Sort or Quick Sort are preferred.

1. Start at the beginning of the array.
2. Assume the first unsorted element is the smallest.
3. Scan the remaining unsorted elements to find the smallest element.
4. Swap the smallest element with the first unsorted element.
5. Repeat the process for the rest of the array until it is sorted.

Worked example

Let us take the following array and apply the Selection Sort algorithm to sort the array in ascending order.

Pass 1

Assume index 0 (6) is the minimum in the unsorted portion of array.

➜ Comparing current minimum 6 at index=0 with 3 at index=1

Found new minimum 3 at index=1.

➜ Comparing current minimum 3 at index=1 with 8 at index=2

No change. 8 is not smaller than current minimum.

➜ Comparing current minimum 3 at index=1 with 2 at index=3

Found new minimum 2 at index=3.

➜ Comparing current minimum 2 at index=3 with 7 at index=4

No change. 7 is not smaller than current minimum.

➜ Comparing current minimum 2 at index=3 with 4 at index=5

No change. 4 is not smaller than current minimum.

➜ Minimum in the unsorted portion of array is 2 at index=3.

Swapping 6 and 2 to place the smallest element at correct position.

Element 2 is now at its correct position.

Pass 2

Assume index 1 (3) is the minimum in the unsorted portion of array.

➜ Comparing current minimum 3 at index=1 with 8 at index=2

No change. 8 is not smaller than current minimum.

➜ Comparing current minimum 3 at index=1 with 6 at index=3

No change. 6 is not smaller than current minimum.

➜ Comparing current minimum 3 at index=1 with 7 at index=4

No change. 7 is not smaller than current minimum.

➜ Comparing current minimum 3 at index=1 with 4 at index=5

No change. 4 is not smaller than current minimum.

➜ Minimum in the unsorted portion of array is 3 at index=1.

No swap needed. Minimum element is already at the correct position.

Element 3 is now at its correct position.

Pass 3

Assume index 2 (8) is the minimum in the unsorted portion of array.

➜ Comparing current minimum 8 at index=2 with 6 at index=3

Found new minimum 6 at index=3.

➜ Comparing current minimum 6 at index=3 with 7 at index=4

No change. 7 is not smaller than current minimum.

➜ Comparing current minimum 6 at index=3 with 4 at index=5

Found new minimum 4 at index=5.

➜ Minimum in the unsorted portion of array is 4 at index=5.

Swapping 8 and 4 to place the smallest element at correct position.

Element 4 is now at its correct position.

Pass 4

Assume index 3 (6) is the minimum in the unsorted portion of array.

➜ Comparing current minimum 6 at index=3 with 7 at index=4

No change. 7 is not smaller than current minimum.

➜ Comparing current minimum 6 at index=3 with 8 at index=5

No change. 8 is not smaller than current minimum.

➜ Minimum in the unsorted portion of array is 6 at index=3.

No swap needed. Minimum element is already at the correct position.

Element 6 is now at its correct position.

Pass 5

Assume index 4 (7) is the minimum in the unsorted portion of array.

➜ Comparing current minimum 7 at index=4 with 8 at index=5

No change. 8 is not smaller than current minimum.

➜ Minimum in the unsorted portion of array is 7 at index=4.

No swap needed. Minimum element is already at the correct position.

Element 7 is now at its correct position.

Array is fully sorted.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    selection_sort(arr)
    print("Sorted array is:", arr)

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 7, 4};
        selectionSort(arr);
        System.out.print("Sorted array is: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

function selectionSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
}
const arr = [6, 3, 8, 2, 7, 4];
selectionSort(arr);
console.log("Sorted array is:", arr);

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int arr[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array is: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int arr[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "Sorted array is: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

package main
import "fmt"

func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIndex := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

func main() {
    arr := []int{6, 3, 8, 2, 7, 4}
    selectionSort(arr)
    fmt.Println("Sorted array is:", arr)
}

fn selection_sort(arr: &mut Vec<i32>) {
    let n = arr.len();
    for i in 0..n - 1 {
        let mut min_index = i;
        for j in (i + 1)..n {
            if arr[j] < arr[min_index] {
                min_index = j;
            }
        }
        arr.swap(i, min_index);
    }
}

fn main() {
    let mut arr = vec![6, 3, 8, 2, 7, 4];
    selection_sort(&mut arr);
    println!("Sorted array is: {:?}", arr);
}

fun selectionSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1) {
        var minIndex = i
        for (j in i + 1 until n) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        val temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    }
}

fun main() {
    val arr = intArrayOf(6, 3, 8, 2, 7, 4)
    selectionSort(arr)
    println("Sorted array is: ${arr.joinToString(" ")}")
}

func selectionSort(_ arr: inout [Int]) {
    let n = arr.count
    for i in 0..<n-1 {
        var minIndex = i
        for j in (i + 1)..<n {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        arr.swapAt(i, minIndex)
    }
}

var arr = [6, 3, 8, 2, 7, 4]
selectionSort(&arr)
print("Sorted array is:", arr)

function selectionSort(arr: number[]): void {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
}

const arr: number[] = [6, 3, 8, 2, 7, 4];
selectionSort(arr);
console.log("Sorted array is:", arr);

Time complexity

Space complexity

O(1)

Bubble sort is performed in-place and only requires a constant amount of additional space for temporary variables used in swapping.