Selection Sort

Selection Sort#

Contents#

Sort \(n\) numbers stored in array \(A[1:n]\) by first finding the smallest element of \(A[1:n]\) and exchanging it with the element in \(A[1]\). Then find the smallest element of \(A[2:n]\) and exchange it with \(A[2]\). Then find the smallest element of \(A[3:n]\) and exchange it with \(A[3]\). Continue in this manner for the first \(n - 1\) elements of \(A\).

 INPUT     an array A[1:n] of n values
OUTPUT    the array A in ascending sorted order

SELECTION_SORT(A, n)
1  for i = 1 to n - 1
2     min_idx = i
3     for j = i + 1 to n
4         if A[j] < A[min_idx]
5             min_idx = j
6     swap(A[i], A[min_idx])

Correctness#

\(\textbf{Invariant}\)

At the end of iteration \(i\), subarray \(A[1:i]\) contains the \(i\) smallest elements of the array \(A\) in ascending sorted order.

\(\textbf{Initialization}\)

\(\textbf{Maintenance}\)

\(\textbf{Termination}\)

Complexity#

Time#

Space#

Implementations#

C#

// selection_sort.c

#include <stdio.h>

void print_array (int A[], int n) {
  for (int i = 0; i < n; i++) {
    printf("%d ", A[i]);
  }
  printf("\n");
}

void swap (int *i, int *min_idx) {
  int temp     = *i;
      *i       = *min_idx;
      *min_idx = temp;
}

void selection_sort (int A[], int n) {
  int min_idx;

  for (int i = 0; i < n - 1; i++) {
    min_idx = i;
    for (int j = i + 1; j < n; j++) {
      if (A[j] < A[min_idx]) {
        min_idx = j;
      }
    }
    swap(&A[i], &A[min_idx]);
  }
}

int main () {
  int A[] = {5, 4, 3, 2, 1};
  int n   = sizeof(A) / sizeof(A[0]);

  print_array(A, n);
  selection_sort(A, n);
  print_array(A, n);

  return 0;
}

Python#

# selection_sort.py

def selection_sort (A, n):
  for i in range(n - 1):
    min_idx = i
    for j in range(i + 1, n):
      if A[j] < A[min_idx]:
        min_idx = j
    A[i], A[min_idx] = A[min_idx], A[i] # swap

A = [5, 4, 3, 2, 1]
n = len(A)

print(A)
selection_sort(A, n)
print(A)

Acknowledgments#

Contents