Selection Sort
- Selection Sort is a
simple comparison-basedsorting 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 thesorted part.
Example 1:
Input: [4, 5, 1, 3, 9]
Output: [1, 3, 4, 5, 9]
Approach:
- Iterate over the array from index
0ton-2. - For each index
i, assume the element atiis theminimumin the unsorted part. - Run an inner loop from
j = i+1 to n-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 at min (if they’re not the same). Repeatuntil the array is sorted.
Time & Space Complexity:
Time Complexity: O(n2) In all cases best, average and worst.
Roughly n*(n-1)/2 comparisons are always performed.
Space Complexity: O(1) Selection Sort is an in-place sorting algorithm, so it doesn’t require extra space.
Dry Run
Input: arr = [4, 5, 1, 3, 9]
i = 0 → min_idx = 0 j = 1 → arr[1] = 5 > arr[0] = 4 → no change j = 2 → arr[2] = 1 < arr[0] = 4 → min_idx = 2 j = 3 → arr[3] = 3 > arr[2] = 1 → no change j = 4 → arr[4] = 9 > arr[2] = 1 → no change swap arr[0] ↔ arr[2] → [1, 5, 4, 3, 9] i = 1 → min_idx = 1 j = 2 → arr[2] = 4 < arr[1] = 5 → min_idx = 2 j = 3 → arr[3] = 3 < arr[2] = 4 → min_idx = 3 j = 4 → arr[4] = 9 > arr[3] = 3 → no change swap arr[1] ↔ arr[3] → [1, 3, 4, 5, 9] i = 2 → min_idx = 2 j = 3 → arr[3] = 5 > arr[2] = 4 → no change j = 4 → arr[4] = 9 > arr[2] = 4 → no change no swap → [1, 3, 4, 5, 9] i = 3 → min_idx = 3 j = 4 → arr[4] = 9 > arr[3] = 5 → no change no swap → [1, 3, 4, 5, 9] Final Sorted Array: [1, 3, 4, 5, 9]
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);
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))
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 + " ");
}
}
}
#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;
}
using System;
class Program
{
static int LinearSearch(int[] arr, int target)
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == target)
{
return i;
}
}
return -1;
}
static void Main()
{
int[] arr = { 4, 5, 1, 3, 9 };
int result = LinearSearch(arr, 5);
Console.WriteLine("Element found at index " + result);
}
}
