Selection Sort Algorithm
Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.
Working of Selection Sort
Selection Sort works by repeatedly finding the smallest (or largest) element from the unsorted part of the array and placing it at the beginning of the sorted part.
Step-by-Step Working:
- Start from the first element.
- Find the minimum element in the entire array.
- Swap it with the first element.
- Now, the first element is sorted.
- Move to the second element and repeat the process for the remaining unsorted part of the array.
- Continue this process until the whole array is sorted.
Example of Selection Sort (According to Image Values)
Given Array:[5, 3, 8, 4, 1, 12, 7]
Pass 1:
Find smallest in [5, 3, 8, 4, 1, 12, 7] → 1
Swap with first element (5)
Result: [1, 3, 8, 4, 5, 12, 7]
Pass 2:
Find smallest in [3, 8, 4, 5, 12, 7] → 3
Already in correct place
Result: [1, 3, 8, 4, 5, 12, 7]
Pass 3:
Find smallest in [8, 4, 5, 12, 7] → 4
Swap with 8
Result: [1, 3, 4, 8, 5, 12, 7]
Pass 4:
Find smallest in [8, 5, 12, 7] → 5
Swap with 8
Result: [1, 3, 4, 5, 8, 12, 7]
Pass 5:
Find smallest in [8, 12, 7] → 7
Swap with 8
Result: [1, 3, 4, 5, 7, 12, 8]
Pass 6:
Find smallest in [12, 8] → 8
Swap with 12
Result: [1, 3, 4, 5, 7, 8, 12]
Final Sorted Array:
[1, 3, 4, 5, 7, 8, 12]
Selection Sort code:
# Selection Sort
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
# Swap
arr[i], arr[min_index] = arr[min_index], arr[i]
def print_array(arr):
for num in arr:
print(num, end=" ")
print()
arr = [64, 25, 12, 22, 11]
print("Before Sorting:")
print_array(arr)
selection_sort(arr)
print("After Sorting:")
print_array(arr)
public class SelectionSort {
// Selection Sort function
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// Print array
public static void printArray(int[] arr) {
for (int num : arr)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("Before Sorting:");
printArray(arr);
selectionSort(arr);
System.out.println("After Sorting:");
printArray(arr);
}
}
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64,25,12,22,11};
int n = 5;
printf("Before Sorting:\n");
printArray(arr, n);
selectionSort(arr, n);
printf("After Sorting:\n");
printArray(arr, n);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
void selectionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
swap(arr[i], arr[minIndex]);
}
}
void printArray(vector<int> arr) {
for (int num : arr)
cout << num << " ";
cout << endl;
}
int main() {
vector<int> arr = {64,25,12,22,11};
cout << "Before Sorting:" << endl;
printArray(arr);
selectionSort(arr);
cout << "After Sorting:" << endl;
printArray(arr);
return 0;
}
Time Complexity of Selection Sort:
| Case | Time Complexity | Explanation |
| Best Case | O(n²) | It still scans the entire array to find the minimum, even if sorted. |
| Average Case | O(n²) | Always performs n(n−1)/2 comparisons regardless of input. |
| Worst Case | O(n²) | No optimization based on input ordering. |
Space Complexity:
- O (1) (in-place sorting, no extra memory used)
Note:
Selection Sort is more efficient than Bubble Sort in terms of swaps (does at most n-1 swaps), but time complexity remains quadratic, making it unsuitable for large datasets.