Selection Sort

Table of Contents

Selection Sort

Selection Sort

Concept: Repeatedly finds the minimum element from the unsorted portion of the array and swaps it with the first unsorted element.

This method is called selection sort because it works by repeatedly selecting the smallest remaining item.

Steps

Find the minimum element in the unsorted part of the array.
Swap it with the first element of the unsorted part.
Repeat steps 1 and 2 until the entire array is sorted.

Selection Sort Pseudocode

The selection sort algorithm divides the input list into two parts: a sorted sublist and an unsorted sublist. The algorithm repeatedly finds the smallest (or largest) element from the unsorted sublist and moves it to the sorted sublist.

Start with the unsorted list: Initialize the sorted sublist as empty and the unsorted sublist as the entire input list.
Iterate through the unsorted list: For each element in the list, from the first index to the second-to-last index (since the last element will automatically be in its correct place after the second-to-last is sorted):
- Find the minimum element: Assume the current element is the minimum. Then, iterate through the rest of the unsorted sublist to find the true minimum value and its index.
- Swap the minimum element: Swap the minimum element found with the current element. This moves the minimum element to its correct, sorted position at the beginning of the unsorted sublist, effectively expanding the sorted sublist by one element.
Repeat until sorted: Continue this process until the entire list is sorted. The sorted sublist will grow by one element with each iteration until all elements are sorted.

Here’s a more detailed, step-by-step breakdown:

function selectionSort(array A, n):  // A is the array, n is the number of elements
  for i from 0 to n-1:
    // Find the minimum element in the unsorted part of the array
    min_idx = i

    for j from i+1 to n:
      if A[j] < A[min_idx]:
        min_idx = j

    // Swap the found minimum element with the first element of the unsorted part
    swap A[i] and A[min_idx]

Example Walkthrough

Let’s say we want to sort the array `[64, 25, 12, 22, 11]`.

First pass:
- The unsorted sublist is `[64, 25, 12, 22, 11]`.
- The minimum element is 11 at index 4.
- Swap 11 with 64.
- The array becomes `[11, 25, 12, 22, 64]`. The sorted part is now `[11]`.
Second pass:
- The unsorted sublist is `[25, 12, 22, 64]`.
- The minimum element is 12 at index 2 (of the original array).
- Swap 12 with 25.
- The array becomes `[11, 12, 22, 25, 64]`. The sorted part is now `[11, 12]`.
Third pass:
- The unsorted sublist is `[22, 25, 64]`.
- The minimum element is 22 at index 2.
- 22 is already in its correct position, so we don’t need to swap.
- The array remains `[11, 12, 22, 25, 64]`. The sorted part is now `[11, 12, 22]`.

This process continues until the entire array is sorted.

Animation of selection sort in action

In each step, the smallest element in the unsorted section is highlighted. That element is swapped with the first element in the unsorted section.

S    E   L   E   |C|   T   I   O   N   S   O   R   T
--|
C | |E|  L   E    S    T   I   O   N   S   O   R   T
  -----|
C    E | L  |E|   S    T   I   O   N   S   O   R   T
       -----|
C    E   E  |L    S    T  |I|  O   N   S   O   R   T
           ----|
C    E   E   I  | S    T  |L|  O   N   S   O   R   T
               ----|
C    E   E   I    L |  T   S   O  |N|  S   O   R   T
                   -----|
C    E   E   I    S    N | S  |O|  T   S   O   R   T
                        ----|
C    E   E   I    S    N   O | S   T   S  |O|  R   T
                            ----|
C    E   E   I    S    N   O   O | T   S   S  |R|  T
                                ----|
C    E   E   I    S    N   O   O   R ||S|  S   T   T
                                    ----|
C    E   E   I    S    N   O   O   R   S ||S|  T   T
                                        ----|
C    E   E   I    S    N   O   O   R   S   S ||T|  T
                                            ----|
C    E   E   I    S    N   O   O   R   S   S   T ||T|
                                                ----|
C    E   E   I    S    N   O   O   R   S   S   T   T |

https://github.com/explorer436/programming-playground/tree/main/java-playground/my-implementations/searching-and-sorting/src/main/java/com/my/company/sorting/algorithms

Time Complexity

O(n^2).

Selection sort uses ~n2/2 compares and n exchanges to sort an array of length n.

Links to this note

Sorting algorithms