Tanishq Rastogi
Posted on Jan 7, 2025 | Coding
Selection Sort
Introduction
Selection Sort is a simple comparison-based algorithm. It selects the smallest(or largest) element from the unsorted portion of the array and place it in correct position.This process is repeated until the array is fully sorted.
Complexity
- Best Case Time Complexity: O(n²)(even when the array is already sorted).
- Average Case Time Complexity: O(n²)
- Worst Case Time Complexity: O(n²)
- Space Complexity: O(1)(in-place sorting).
Algorithm Steps
- Start with the first element of the unsorted array.
- Select the minimum element in the unsorted part of the array.
- Swap it with the first unsorted element.
- Ignore the sorted part of the array for next steps.
- Repeat the process until the entire array is sorted.
Example
Let's take example of array whose elements are: [5][3][8][4][2].
Pass 1:
- Current array:[5][3][8][4][2]
- Select the first element of unsorted array to be smallest -> [5]
- Compare [5] with all unsorted elements to find the smallest:
- Compare 5 and 3 => 3 is smaller.
- Compare 3 and 8 => 3 is smaller.
- Compare 3 and 4 => 3 is smaller.
- Compare 3 and 2 => 2 is smaller.
- Smallest element is 2.
- Swap(5,2).
- Updated array:[2][3][8][4][5].
- Now for next pass, we can ignore the first element(i.e.2) as it is already sorted.
Pass 2:
- Current array:[3][8][4][5]
- Select the first element of unsorted array to be smallest -> [3]
- Compare [3] with all unsorted elements to find the smallest:
- Compare 3 and 8 => 3 is smaller.
- Compare 3 and 4 => 3 is smaller.
- Compare 3 and 5 => 3 is smaller.
- Smallest element is 3.
- Swap(3,3).(3 is already in it's place).
- Updated array:[3][8][4][5].
- Now for next pass, we can ignore the first element (i.e 3)as it is already sorted.
Pass 3:
- Current array:[8][4][5]
- Select the first element of unsorted array to be smallest -> [8]
- Compare [8] with all unsorted elements to find the smallest:
- Compare 8 and 4 => 4 is smaller.
- Compare 4 and 5 => 4 is smaller.
- Smallest element is 4.
- Swap(8,4).
- Updated array:[4][8][5].
- Now for next pass, we can ignore the first element (i.e 4)as it is already sorted.
Pass 4:
- Current array:[8][5]
- Select the first element of unsorted array to be smallest -> [8]
- Compare [8] with all unsorted elements to find the smallest:
- Compare 8 and 5 => 5 is smaller.
- Smallest element is 5.
- Swap(8,5).
- Updated array:[5][8], all the elements are now in sorted form.
Sorted array: [2][3][4][5][8]
Note: In paper you have to write every element in each pass and draw a line to seperate sorted array with the unsorted one.
Key Observation
- In each pass, the smallest element from the unsorted part is moved to its correct position.
- The number of unsorted elements decreases by one after each pass.
- Selection Sort performs the same number of comparisons in every case, regardless of whether the array was partially sorted.
- After n-1 passes (where n is the size of the array), the array is fully sorted.
Advantages
- Simple and easy to understand algorithm.
- Requires no extra space (in-place sorting).
- Performs well on small datasets.
- Useful when memory writes are expensive, as it minimizes swaps.
Disadvantages
- Inefficient for large datasets.
- Time complexity remains O(n²) even for a nearly sorted array.
- It is unstable (relative order of equal elements may change).
- Too many comparisons make it slower than more advanced algorithms (like Merge Sort or Quick Sort).
Code in C:
#include<stdio.h>
void main(){
int arr[100]; // consider the size of array 100
int n;
printf("enter the size of array\n");
scanf("%d",&n);
printf("enter the array elements\n");
for(int i=0; i<n; i++{
scanf("%d",&arr[i]);
}
// unsorted array--
printf("unsorted array is :\n");
for(int i=0; i<n; i++{
printf("%d ",arr[i]);
}
// Selection sort--
for(int i=0; i<n-1; i++){
int min_Idx = i; // Minimum or smallest element
for(int j = i+1; j<n; j++){
if(arr[j] < arr[min_Idx]){
min_Idx = j; // update the minimum element
}
}
// swap the minimum element to correct position--
int temp = arr[i];
arr[i] = arr[min_Idx];
arr[min_Idx] = temp;
}
// sorted array--
printf("sorted array is : ");
for(int i=0; i<n; i++{
printf("%d ",arr[i]);
}
}
Code in C++:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cout<<"enter the size of array"<<endl;
cin>>n;
int arr[n];
cout<<"enter the array elements"<<endl;
for(int i=0;i<n;i++)
cin>>arr[i];
cout<<"unsorted array is :"<<endl;
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
//selection sort method
for (int i = 0; i < n - 1; i++) {
int minIndex = i; // Assume the first unsorted element is the smallest
// Find the minimum in the unsorted part
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum with the first unsorted element
swap(arr[minIndex], arr[i]);
}
cout<<endl<<"sorted array is : ";
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
return 0;
}
Note: swap(val1,val2) is an in-built function in C++ (not in C) to swap two values.
Code in JAVA:
import java.util.Scanner;
class Solution{
public static void main(String[] args){
Scanner sc = new Scanner(System.in); // scanning the input
System.out.println("enter size of array:");
int n = sc.nextInt();
int[] arr = new int[n]; // Initialize an array
System.out.println("enter the elements:");
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
// Printing Unsorted Array--
System.out.println("unsorted elements are:");
for(int i=0; i<n; i++){
System.out.print(arr[i]+" ");
}
// Selection sort--
for(int i=0; i<n-1; i++){
int min_Idx = i; // Minimum or smallest element
for(int j = i+1; j<n; j++){
if(arr[j] < arr[min_Idx]){
min_Idx = j; // update the minimum element
}
}
// swap the minimum element to correct position--
int temp = arr[i];
arr[i] = arr[min_Idx];
arr[min_Idx] = temp;
}
// Printing Sorted Array--
System.out.println("sorted elements are:");
for(int i=0; i<n; i++){
System.out.print(arr[i]+" ");
}
}
}
Output
enter the size of array
5
enter the array elements
5 3 8 4 2
unsorted array is :
5 3 8 4 2
sorted array is : 2 3 4 5 8
More on Sorting:
6 Reactions
0 Bookmarks