Selection Sort Algorithm with Space & Time Complexity

by

Selection Sort is a simple sorting algorithm that works by selecting the smallest element from the unsorted list and swapping it with the leftmost unsorted element. This process is repeated until the entire list is sorted.

The space and Time complexity is exactly like the Bubble Sort and Insertion Sort Algorithm.

Learn Quick Sort Algorithm faster than any brute force Sorting.

Keep Learning.

Complexity Analysis

Time Complexity

The time complexity of the Selection Sort algorithm is O(n^2) in all cases, where n is the number of elements in the array. It is not suitable for large datasets.

Space Complexity

It has the advantage of requiring only a constant amount of additional memory space. That’s why, Time Complexity is O(1).

Algorithm Implementation With C++

#include <iostream>
using namespace std;

void Selection_sort(int Arr[], int n){
    for(int i=0; i<n; 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;
            }
        }
    }

    cout<<"The Sorted Array are"<<endl;
    for(int i=0; i<n; i++)
    {
        cout<<Arr[i]<<' ';
    }
}

int main(){
    int Arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(Arr)/sizeof(Arr[0]);

    Selection_sort(Arr,n);

    return 0;
}

Code Explanation

Consider an array of unsorted integers: [64, 25, 12, 22, 11]

First, the algorithm will find the smallest element in the entire array, which is 11. It will swap 11 with the first element in the array, resulting in the array: [11, 25, 12, 22, 64]

Next, the algorithm will find the smallest element in the remaining unsorted subarray, which is 12. It will swap 12 with the second element in the array, resulting in the array: [11, 12, 25, 22, 64]

This process will continue until the entire array is sorted: [11, 12, 22, 25, 64]

Thanks For Visiting. Keep Learning.

Leave a Comment