Selection Sort

Definition

Definition

Selection Sort is a simple comparison-based sorting algorithm that divides the input list into two parts: a sorted sublist and an unsorted sublist. It repeatedly selects the smallest (or largest) element from the unsorted sublist and swaps it with the leftmost unsorted element, moving the sublist boundaries one element to the right

Explanation

Iterate through the input list and repeatedly selecting the smallest element from the unsorted part and moving it to the beginning. This is done by maintaining two sublists within the array: the sorted sublist and the unsorted sublist. Initially, the entire array is unsorted. In each iteration, the algorithm finds the minimum element from the unsorted sublist and swaps it with the first unsorted element, thereby expanding the sorted sublist by one element and shrinking the unsorted sublist by one element. This process continues until the entire array is sorted

Guidance

• Start with the first element as the current minimum
  • Compare this minimum element with the rest of the elements in the array
  • If any element is found smaller than the current minimum, update the minimum element
  • After completing the comparison, swap the current minimum element with the first unsorted element
  • Now, the first element of the array is in its correct sorted position
  • Repeat steps for the remaining unsorted portion of the array, each time considering only the unsorted portion for finding the minimum element
• Continue this process until the entire array is sorted

Tips

• remember that it's not the most efficient sorting algorithm for large datasets. It's mainly used for educational purposes or when simplicity is favored over efficiency
• selection sort is an in-place sorting algorithm, meaning it doesn't require extra space for sorting
• the algorithm involves a lot of swapping, so keep track of the indices and values being swapped properly to avoid errors

Practice

Practice

selectionSort(array A)
  n = length of A
  for i from 0 to n-1
    minIndex = i
    for j from i+1 to n-1
      if A[j] < A[minIndex]
        minIndex = j
      swap A[i] with A[minIndex] // Swap the minimum element with the first unsorted element

Solution

package main

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]
    }
}

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;
    }
  }
}

function selectionSort(arr) {
  const 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;
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
}

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
    }
}

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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]

fn selection_sort(arr: &mut [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);
    }
}

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