Selection Sort - Algorithm, Visualization, Examples

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode Detailed Exmpl

Problem Statement❯

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.

Examples❯

Input Array Sorted Output Description
[64, 25, 12, 22, 11] [11, 12, 22, 25, 64] Unsorted array with multiple elementsVisualization
[1, 2, 3, 4, 5] [1, 2, 3, 4, 5] Already sorted arrayVisualization
[5, 4, 3, 2, 1] [1, 2, 3, 4, 5] Reverse sorted arrayVisualization
[1] [1] Single-element array remains unchangedVisualization
[] [] Empty array has nothing to sort
[7, 7, 7, 7] [7, 7, 7, 7] All elements are equalVisualization
[3, -1, 0, -5, 2] [-5, -1, 0, 2, 3] Array with negative and positive numbersVisualization

Visualization Player

Solution❯

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.

Algorithm Steps❯

  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.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
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)

Detailed Step by Step Example❯

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

{ "array": [6,3,8,2,7,4], "showIndices": true, "specialIndices": [] }

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

{ "array": [6,3,8,2,7,4], "showIndices": true, "highlightIndices": [0,1], "highlightIndicesGreen": [], "specialIndices": [], "labels": { "0": "min" } }

Found new minimum 3 at index=1.

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

{ "array": [6,3,8,2,7,4], "showIndices": true, "highlightIndices": [1,2], "highlightIndicesGreen": [], "specialIndices": [], "labels": { "1": "min" } }

No change. 8 is not smaller than current minimum.

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

{ "array": [6,3,8,2,7,4], "showIndices": true, "highlightIndices": [1,3], "highlightIndicesGreen": [], "specialIndices": [], "labels": { "1": "min" } }

Found new minimum 2 at index=3.

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

{ "array": [6,3,8,2,7,4], "showIndices": true, "highlightIndices": [3,4], "highlightIndicesGreen": [], "specialIndices": [], "labels": { "3": "min" } }

No change. 7 is not smaller than current minimum.

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

{ "array": [6,3,8,2,7,4], "showIndices": true, "highlightIndices": [3,5], "highlightIndicesGreen": [], "specialIndices": [], "labels": { "3": "min" } }

No change. 4 is not smaller than current minimum.

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

{ "array": [6,3,8,2,7,4], "showIndices": true, "highlightIndices": [3], "highlightIndicesGreen": [], "specialIndices": [] }

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

{ "array": [2,3,8,6,7,4], "showIndices": true, "highlightIndices": [0,3], "highlightIndicesGreen": [0], "specialIndices": [] }

Element 2 is now at its correct position.

{ "array": [2,3,8,6,7,4], "showIndices": true, "highlightIndicesGreen": [0], "specialIndices": [] }

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

{ "array": [2,3,8,6,7,4], "showIndices": true, "highlightIndices": [1,2], "highlightIndicesGreen": [0], "specialIndices": [], "labels": { "1": "min" } }

No change. 8 is not smaller than current minimum.

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

{ "array": [2,3,8,6,7,4], "showIndices": true, "highlightIndices": [1,3], "highlightIndicesGreen": [0], "specialIndices": [], "labels": { "1": "min" } }

No change. 6 is not smaller than current minimum.

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

{ "array": [2,3,8,6,7,4], "showIndices": true, "highlightIndices": [1,4], "highlightIndicesGreen": [0], "specialIndices": [], "labels": { "1": "min" } }

No change. 7 is not smaller than current minimum.

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

{ "array": [2,3,8,6,7,4], "showIndices": true, "highlightIndices": [1,5], "highlightIndicesGreen": [0], "specialIndices": [], "labels": { "1": "min" } }

No change. 4 is not smaller than current minimum.

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

{ "array": [2,3,8,6,7,4], "showIndices": true, "highlightIndices": [1], "highlightIndicesGreen": [0], "specialIndices": [] }

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

Element 3 is now at its correct position.

{ "array": [2,3,8,6,7,4], "showIndices": true, "highlightIndicesGreen": [0,1], "specialIndices": [] }

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

{ "array": [2,3,8,6,7,4], "showIndices": true, "highlightIndices": [2,3], "highlightIndicesGreen": [0,1], "specialIndices": [], "labels": { "2": "min" } }

Found new minimum 6 at index=3.

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

{ "array": [2,3,8,6,7,4], "showIndices": true, "highlightIndices": [3,4], "highlightIndicesGreen": [0,1], "specialIndices": [], "labels": { "3": "min" } }

No change. 7 is not smaller than current minimum.

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

{ "array": [2,3,8,6,7,4], "showIndices": true, "highlightIndices": [3,5], "highlightIndicesGreen": [0,1], "specialIndices": [], "labels": { "3": "min" } }

Found new minimum 4 at index=5.

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

{ "array": [2,3,8,6,7,4], "showIndices": true, "highlightIndices": [5], "highlightIndicesGreen": [0,1], "specialIndices": [] }

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

{ "array": [2,3,4,6,7,8], "showIndices": true, "highlightIndices": [2,5], "highlightIndicesGreen": [0,1,2], "specialIndices": [] }

Element 4 is now at its correct position.

{ "array": [2,3,4,6,7,8], "showIndices": true, "highlightIndicesGreen": [0,1,2], "specialIndices": [] }

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

{ "array": [2,3,4,6,7,8], "showIndices": true, "highlightIndices": [3,4], "highlightIndicesGreen": [0,1,2], "specialIndices": [], "labels": { "3": "min" } }

No change. 7 is not smaller than current minimum.

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

{ "array": [2,3,4,6,7,8], "showIndices": true, "highlightIndices": [3,5], "highlightIndicesGreen": [0,1,2], "specialIndices": [], "labels": { "3": "min" } }

No change. 8 is not smaller than current minimum.

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

{ "array": [2,3,4,6,7,8], "showIndices": true, "highlightIndices": [3], "highlightIndicesGreen": [0,1,2], "specialIndices": [] }

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

Element 6 is now at its correct position.

{ "array": [2,3,4,6,7,8], "showIndices": true, "highlightIndicesGreen": [0,1,2,3], "specialIndices": [] }

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

{ "array": [2,3,4,6,7,8], "showIndices": true, "highlightIndices": [4,5], "highlightIndicesGreen": [0,1,2,3], "specialIndices": [], "labels": { "4": "min" } }

No change. 8 is not smaller than current minimum.

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

{ "array": [2,3,4,6,7,8], "showIndices": true, "highlightIndices": [4], "highlightIndicesGreen": [0,1,2,3], "specialIndices": [] }

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

Element 7 is now at its correct position.

{ "array": [2,3,4,6,7,8], "showIndices": true, "highlightIndicesGreen": [0,1,2,3,4], "specialIndices": [] }

Array is fully sorted.

{ "array": [2,3,4,6,7,8], "showIndices": true, "highlightIndicesGreen": [0,1,2,3,4,5], "specialIndices": [] }