In the selection sort algorithm in data structures, the smallest element is searched in the array, and placed in the first position. Then, excluding the first position, the smallest element is searched in the remaining array and placed in the second position. This continues till all the elements are in their correct positions.
To understand this, let us consider an unsorted array –
First, the smallest element is searched in the array. After searching, the smallest element is found to be 3. So, element 3 is swapped with the first element which is 9.
Now, in the second iteration, the smallest element is searched in the remaining array. This search will not include 3 now, because it is set at its correct position.
The smallest element in this array is now found to be 5. So, 5 is swapped with the element at the second position.
Now, the smallest element is found in the array excluding the first two positions. This is now found to be 9. So, 9 is now swapped with the element at the third position.
Now, the smallest element is found in the array excluding the first three positions. This is found to be 12 now. So, 12 is swapped with the element at the 4th position.
The array is now sorted. So, selection sort each time selects the smallest and puts it at the start of the array.
Now, we will understand the codes for this –
#include <bits/stdc++.h>
using namespace std;
void swap(int *xp, int *yp)
{ int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{ int i, j, min_idx;
for (i = 0; i < n-1; i++)
{
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
if(min_idx!=i)
swap(&arr[min_idx], &arr[i]);
}
}
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = {9,3,12,18,5};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
Output –
3,5,9,18,12
Time complexity Analysis –
The time complexity for the selection sort algorithm is O(n^2) because each time n comparisons are made. And there are n iterations required to sort the array.
Space Complexity Analysis –
O(1) as the only extra memory used is for temporary variables while swapping two values in Array. The selection sort never makes more than O(N) swaps and can be useful when memory write is a costly operation.
So, in this article, we learned about the selection sort algorithm which is one of the algorithms to sort the elements in the array.
Try these Quizzes
Fundamentals of Data Structures Quiz
