Selection Sorting in Data Structure

Selection Sort can be defined as finding the least value in the array, swapping it into the leftmost component and then forgetting the leftmost component, do this repeatedly.

Selection Sorting in Data Structure

Algorithm for Selection Sort:

Algorithm fnSelectionSort(P[], n)
{
for(k=0;k<n-1; k++)
{
loc=k;
for(j=k+1; j<n; j++)
if(P[j]<P[loc])
loc=j;
if(loc!=k)
{
temp=P[k];
P[k]=P[loc];
P[loc]=temp;
}
}
} // End of Algorithm

Time complexity of Selection Sort:

1. Best Case: The best occurs when the list is in the desired order. But unfortunately to get the minimum element from a set of n-k elements n-k comparisons are required. So, for the first iteration, we have to go through n-1 elements and hence n-1 comparisons. Similarly, for the second iteration, n-2 comparisons are needed and so on. Thus,
f(n)=n(n-1)+(n-2)+…….+1
=n(n-1)/2
Therefore, T(n)=O(n2)

2. Average Case: Here also in the first iteration n-1 comparisons are required, in the second iteration n-2 comparisons and so on.
f(n)=(n-1)+(n-2)+…….+1
Therefore, T(n)=O(n2)

3. Worst Case: Like the best case and average case here also,
f(n)=(n-1)+(n-2)+……+1
=n(n-1)/2
Therefore, T(n)=O(n2)

Space complexity of Selection Sort:

The space complexity is O(1). Here also we don’t count the size of the array being sorted because that is given, not created specifically for this algorithm.