Selection Sort is a simple comparison-based sorting algorithm. It divides the array into two parts: a sorted subarray and an unsorted subarray. Initially, the sorted part is empty, and the unsorted part is the entire array. In each iteration, it finds the minimum element from the unsorted part and moves it to the end of the sorted part.
Example:
For input [4, 5, 1, 3, 9], the sorted output will be [1, 3, 4, 5, 9].
Approach:
- Iterate over the array from index 0 to n-2.
- For each index
i, assume the element atiis the minimum in the unsorted part. - Run an inner loop from
j = i+1ton-1to find the actual minimum element. - If a smaller element is found, update the min index.
- After the inner loop, swap the element at
iwith the element atmin(if they’re not the same). - Repeat until the array is sorted.
Dry Run (Example: [4, 5, 1, 3, 9])
- Start from index 0 → Find the smallest element → it’s 1. Swap with 4 → [1, 5, 4, 3, 9]
- Index 1 → Smallest from index 1 → 3. Swap with 5 → [1, 3, 4, 5, 9]
- Index 2 → Smallest is 4 → already in place → [1, 3, 4, 5, 9]
- Index 3 → Smallest is 5 → already in place → [1, 3, 4, 5, 9]
Time Complexity (TC):
- O(n²) in all cases — best, average, and worst.
- Roughly n*(n-1)/2 comparisons are always performed.
Space Complexity (TC):
O(1)
Selection Sort is an in-place sorting algorithm, so it doesn’t require extra space.
let arr = [4, 5, 1, 3, 9];
function selectionSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
let min = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
return arr;
}
let result = selectionSort(arr);
console.log("Sorted array", result);
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
int main() {
int arr[] = {4, 5, 1, 3, 9};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
int main() {
int arr[] = {4, 5, 1, 3, 9};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
public class Main {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {4, 5, 1, 3, 9};
selectionSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
def selectionSort(arr):
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
arr = [4, 5, 1, 3, 9]
print("Sorted array", selectionSort(arr))
