Summary
| Algorithm Name | Selection Sort | |
| Category |  Sorting Algorithms | |
| Core Technique | Repeatedly select the smallest element from the unsorted part and place it at the beginning. | |
| Best Case Time Complexity | Ω(n^2) | Quadratic |
| Average Case Time Complexity | Θ(n^2) | Quadratic |
| Worst Case Time Complexity | O(n^2) | Quadratic |
| Space / Memory Complexity | O(1) | In-place |
Intro
Selection sort is a comparison-based sorting algorithm. It works by repeatedly finding the smallest element from the unsorted part of the array, and placing it at the beginning.
It is easy to understand and implement the algorithm, but it has a time complexity of O(n^2). So, very inefficient for large datasets.
Use Cases
Selection sort is not a very efficient algorithm(with the complexity of O(n^2), so there are no significant real-world use cases we can recommend for this algorithm.
Mostly used for educational purposes or to explore the sorting mechanism.
Algorithm Visualizer
Enter integers separated by commas(Example: 5,3,8,4,2,7,1,9,6).
Click ‘Start Sorting’ to visualize selection sort.
Click ‘Reset’ to clear and re-enter numbers.
Click ‘Start Sorting’ to visualize selection sort.
Click ‘Reset’ to clear and re-enter numbers.
Selection Sort Visualizer Logs…
Implementation Steps
Here are the steps we should follow to implement the Selection sort algorithm-
- Start with the first element and assume it is the smallest element(for now).
- Keep this field as the selected position.
- Search the unsorted part(rest of the) array.
- Find the smallest element in that part.
- Swap the smallest element with the item in the selected position.
- Move the selected position to the next index.
- Repeat Step #2 to Step #4 for the remaining elements.
- Continue until it reaches the second last element.
- As we do not need to go to the last element. The last element will be processed when we reach the second last element.
Pseudocode
Here is the pseudocode for Selection sort. It will make the implementation steps clear-
// Selection Sort Pseudocode
procedure SelectionSort(array A)
n = length(A)
for i from 0 to n-2 do
minIndex = i
// Find the index of the smallest element in the unsorted part
for j from i+1 to n-1 do
if A[j] < A[minIndex] then
minIndex = j
end if
end for
// Swap the smallest element with the element at index i
if minIndex != i then
swap A[i] and A[minIndex]
end if
end for
end procedureImplementation
// Selection Sort implementation
/**
* Selection Sort Algorithm
* @param {number[]} arr - The array to be sorted
* @returns {number[]} - The sorted array
*/
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minElemIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minElemIdx]) {
minElemIdx = j;
}
}
if (minElemIdx !== i) {
// Swap using array destructuring
[arr[i], arr[minElemIdx]] = [arr[minElemIdx], arr[i]];
// Or use a temporary variable
// let temp = arr[i];
// arr[i] = arr[minElemIdx];
// arr[minElemIdx] = temp;
}
}
return arr;
}
export default selectionSort;Demo
import selectionSort from "./selection-sort.js";
// Demo cases
const demoCases = [
{ name: "Random order", arr: [5, 3, 8, 4, 2] },
{ name: "Already sorted", arr: [1, 2, 3, 4, 5] },
{ name: "Reverse sorted", arr: [5, 4, 3, 2, 1] },
{ name: "With duplicates", arr: [3, 1, 2, 3, 2, 1] },
{ name: "Single element", arr: [42] },
{ name: "Empty array", arr: [] }
];
demoCases.forEach(({ name, arr }) => {
const inputArr = [...arr];
const sortedArr = selectionSort(inputArr);
console.log(`\nCase: ${name}`);
console.log("Input Array:", arr);
console.log("Sorted Array:", sortedArr);
});Output:
Case: Random order
Input Array: [ 5, 3, 8, 4, 2 ]
Sorted Array: [ 2, 3, 4, 5, 8 ]
Case: Already sorted
Input Array: [ 1, 2, 3, 4, 5 ]
Sorted Array: [ 1, 2, 3, 4, 5 ]
Case: Reverse sorted
Input Array: [ 5, 4, 3, 2, 1 ]
Sorted Array: [ 1, 2, 3, 4, 5 ]
Case: With duplicates
Input Array: [ 3, 1, 2, 3, 2, 1 ]
Sorted Array: [ 1, 1, 2, 2, 3, 3 ]
Case: Single element
Input Array: [ 42 ]
Sorted Array: [ 42 ]
Case: Empty array
Input Array: []
Sorted Array: []Tests
import { describe, it, expect } from "vitest";
import selectionSort from "./selection-sort.js";
describe("Selection Sort", () => {
it("should sort an array of numbers in ascending order", () => {
const sortedArr = selectionSort([5, 3, 8, 4, 2]);
expect(sortedArr).toEqual([2, 3, 4, 5, 8]);
});
it("should handle an already sorted array", () => {
const sortedArr = selectionSort([1, 2, 3, 4, 5]);
expect(sortedArr).toEqual([1, 2, 3, 4, 5]);
});
it("should handle an array with duplicate values", () => {
const sortedArr = selectionSort([3, 1, 2, 3, 2, 1]);
expect(sortedArr).toEqual([1, 1, 2, 2, 3, 3]);
});
it("should handle an empty array", () => {
const sortedArr = selectionSort([]);
expect(sortedArr).toEqual([]);
});
it("should handle an array with a single element", () => {
const sortedArr = selectionSort([42]);
expect(sortedArr).toEqual([42]);
});
it("should handle an array with all identical elements", () => {
const sortedArr = selectionSort([7, 7, 7, 7]);
expect(sortedArr).toEqual([7, 7, 7, 7]);
});
it("should handle an array with negative numbers", () => {
const sortedArr = selectionSort([3, -1, -4, 2, 0]);
expect(sortedArr).toEqual([-4, -1, 0, 2, 3]);
});
it("should handle an array with very large and very small numbers", () => {
const sortedArr = selectionSort([999999, -999999, 0, 1, -1]);
expect(sortedArr).toEqual([-999999, -1, 0, 1, 999999]);
});
it("should handle an array with non-integer numbers", () => {
const sortedArr = selectionSort([2.5, 3.1, 1.2, 4.8]);
expect(sortedArr).toEqual([1.2, 2.5, 3.1, 4.8]);
});
it("should handle an array with only two elements", () => {
const sortedArr = selectionSort([2, 1]);
expect(sortedArr).toEqual([1, 2]);
});
it("should handle an array with a single repeated value and others", () => {
const sortedArr = selectionSort([1, 2, 1, 3, 1]);
expect(sortedArr).toEqual([1, 1, 1, 2, 3]);
});
});Source Code
| Source Code of | Implementation Code | Demo Code | Test Case Code | Benchmark Code |
|---|---|---|---|---|
| Selection Sort Visualizer | Selection Sort Visualizer – GitHub | |||
| Selection Sort Pseudocode | Selection Sort Pseudocode – GitHub | |||
| Selection Sort Implementation in JS | Selection Sort Implementation in JS – GitHub | Selection Sort Demo in JS – GitHub | Selection Sort Tests in JS – GitHub | Selection Sort Benchmark in JS – GitHub |