Here, you’ll get thorough info about writing a program using a selection sort algorithm, while implementing an example. This is one of the simplest algorithms for sorting arrays. Its disadvantages are relating to time complexity which will be discussed further.
We are tasked to create a sorted array of elements from a given random array, the simple solution of traversing the array and choosing the smallest element and placing it in the front, and then we repeat this process n-1 times to place all the elements of the array in sorted order.
Table of Contents
Algorithm Approach:
In this approach we repeatedly look for the smallest element in subarrays and start placing them at the front end of the same, this way, we are guaranteed to have a sorted array after completing the nested loop
void selectionSort(int *A,int n) //function declaration
{
for(int i=0;i<n-1;i++) //outer loop call till second last element
{
int min=i; //initializing min variable for inner loop
for(int j=i+1;j<n;j++) //inner loop from next element
{
if(A[min]>A[j]) //if given element is smaller, update
min=j;
}
swap(A[i],A[min]); //swap min with the current ith element
}
}
int main() {
int arr[]={1,7,0,9,22,4};
selectionSort(arr,6);
for(int i=0;i<6;i++)
cout<<arr[i]<<" ";
}
Output:
0 1 4 7 9 22
Explanation for the selection sort algorithm
For the above given array, consider the code and look at the following image:
- 0 is the smallest and is in the first place thus no swapping takes place.
- 1 is the smallest element hence elements at index 2,1 are swapped.
- 4 is the smallest element hence elements at index 5,2 are swapped.
- 7 is the smallest element hence elements at index 5,3 are swapped.
- 9 is the smallest element hence elements at index 5,4 are swapped.
As we have completed the traversal the loop exits and as the function uses pass by reference we need not return anything, hence the output is sorted array as shown.
Time Complexity of the program for selection sort
As we have nested loops in the algorithm, we can say that the time complexity will be O(n^2). This is relatively high and thus this is not implemented in rather large datasets, for improving the time complexity we can look for other algorithms listed at the end.
Space Complexity of the program for selection sort
As arrays are passed by reference, and there aren’t any temporary data structures created that are dependent on n, thus the auxiliary space required for the execution of the code is O(1). It is constant.
Other sorting algorithms:
You can go through the following algorithms for