The Main Idea
To understand the selection sort time complexity one's has to understand the implementation of selection sort. The implementation of selection sort is discussed in this link.
The implementation and main logic of selection sort are the same as bubble sort. For better understanding, the main logic behind those algorithms is shown below.
Bubble sort main idea:
for (i=1; i<=n; i++)
{
for (j=1; j<n; j++)
{
if (DataArray[j+1] < DataArray[j])
{
temp = DataArray[j];
DataArray[j] = DataArray[j+1];
DataArray[j+1] = temp;
}
}
}
Selection sort main idea:
for (i=0; i<n; i++)
{
for (j=i+1; j<=n; j++)
{
if (DataArray[i]>DataArray[j])
{
swap(DataArray[i], DataArray[j]);
}
}
}
Selection Sort Time Complexity
As we discussed before, the time complexity of an algorithm is mostly dependent on the input size and the number of loops runs for the input array length size. The main idea implementation of selection sort clearly shows the use of two loops for the comparison of the data array. So it simply can be said that the time complexity of selection sort is O (n2). Then what will be the complexity of the input size of selection sort? It is simple, that is O (1). Because we are normally taking inputs. The time complexity of selection sort is a little bit less than the other O(n2) time complexity sorting algorithms. Because the inner loop for the comparison of the selection sort starts for i-the index instead of the first index of the data array. But, this little bit less code running time doesn't affect the O(n2) time complexity. Finally, the time complexity is,
Time Complexity = Input taking * Comparison of elements
= O (1) * O (n2)
= O (n2)
Time Complexity of Selection Sort is O(n2)
Read Similar Posts:
3. Insertion Sort Time Complexity