Selection Sort Algorithm in C++

The Selection Sort Algorithm is one of the popular sorting algorithms that is used to arrange the array of elements in sorted order either in ascending or descending order. 

In the selection sort algorithm (considering ascending order), we repeatedly find the smallest element from the unsorted part of the array and put them at the beginning. In every iteration, we divide the given array into a sorted and unsorted part and we move the smallest element from the unsorted part to the sorted part. 

Working of Selection Sort Algorithm.

Steps for Selection Sort Algorithm:

• Initialize a min_index value with the initial index as 0.
• Traverse the array to find the index of the minimum value of the given array. 
• If any index value is smaller than min_index is found then we will swap both the value. It might be possible that more than one smaller value is present in that case you need to pick the smallest one only.
• In the next iteration increment the min_index so it will point to the next value and then again start traversing the unsorted part (right-hand side of min_index) of the array to get the next smaller value.
• Keep repeating the above steps until the entire array gets sorted. 

Below is the C++ Code Implementation for Selection Sort Algorithm.

//Program for Selection sort algorithm in C++
#include<iostream>
using namespace std;

void selectionSort(int arr[], int n){
    int min_index;

    //First loop keep on descreasing the size 
    //of unsorted array
    for(int i = 0; i < n-1; i++){
        min_index = i;
        //Second loop to find the smalles element
        //from unsorted subarray
        for(int j = i+1; j < n; j++){
            if(arr[j] < arr[min_index])
                min_index = j;
        }
        //swape the minimum element with ith element
        if(min_index != i)
            swap(arr[i], arr[min_index]);
    }
}

int main(){
    int arr[] = {10, 23, 5, 8, 21, 15};
    int n = sizeof(arr)/sizeof(arr[0]);

    selectionSort(arr, n);

    cout<<"Sorted Array:";
    for(int i = 0; i < n; i++){
        cout<<arr[i]<<" ";
    }
}

Output:

Sorted Array:5 8 10 15 21 23

Time Complexity: The Time complexity of the Selection Sort Algorithm is O(n^2) as we are using two nested loops one is for selecting the current minimum element and the next loop is to find the minimum element out of the remaining unsorted array. 

Space Complexity: The Space complexity of the Selection sort is O(1) as we are not using any extra space for storing any kind of value except min_index and two swapping values.

See more:

(getButton) #text=(Insertion Sort Algorithm) #icon=(link) #color=(#2339bd)

(getButton) #text=(Bubble Sort Algorithm) #icon=(link) #color=(#2339bd)

(getButton) #text=(Merge Sort Algorithm) #icon=(link) #color=(#2339bd)

(getButton) #text=(Quick Sort Algorithm) #icon=(link) #color=(#2339bd)