Selection Sort Algorithm

Selection sort is an in-place sorting algorithm that works on the notion of finding the minimum element(if sorting in ascending order) or maximum element(if sorting in descending order) in the unsorted array and placing it in its correct position.

It divides the entire unsorted array into two subarrays: sorted and unsorted. In every iteration, it picks the minimum/maximum element from the unsorted subarray and places it in the sorted subarray. Hence it runs n times.

Let’s understand how selection sort works

1. Start from the first element and search for the smallest element in the entire array.
2. Replace the minimum element with the first element of the array.
3. Repeat steps 1 and 2 for each element until the entire array is no sorted.

Algorithm

Following is the algorithm for selection sort.

selection_sort( arr ){
    for i in range 0 to (n-1){
        min = i;
        for j in range (i+1) to (n-1){
            if(arr[j] < arr[min])
                min = j;
        }
        swap(arr[i],arr[j]);
    }
    return arr;
}

Implementation in CPP

#include <bits/stdc++.h>
using namespace std;

void swap(int *m, int *n){
	int temp;
	temp = *m;
	*m = *n;
	*n = temp;
}

int selection_sort(int *arr, int n){

	int min_index;

	for(int i=0; i<n; i++)
	{
		min_index = i;
		for(int j=i+1; j<n; j++)
		{
			if(arr[min_index]>arr[j])
				min_index = j;
		}
		swap(&arr[min_index], &arr[i]);
	}
	return 0;
}

int main(){

	int arr[] = {5,8,4,1,2};
	int arr_size = sizeof(arr)/sizeof(arr[0]);

	selection_sort(arr, arr_size);
	
	cout<<"Sorted array = ";
	for(int i=0; i<arr_size; i++)
		cout<<arr[i]<<" ";
	cout<<endl;
	
	return 0;
}

Time Complexity

The time complexity of the above algorithm in the worst case is O(N²), and O(N) in the best case i.e, when the entire array will be sorted.

Remember:
1. Best case time complexity = O(N²)
2. Worst-case time complexity = O(N²)
3. Auxiliary space requirement = O(1)
4. The total number of swaps done = O(N).

Did, we miss something, or do you want to add some other key points?
Please comment.