Selection Sort
For a general definition of time complexity, see this page.
Selection Sort Time Complexity
The Selection Sort algorithm iteratively sorts an array by going through each element, determining which has the lowest value, and then pushing that element to the front. This process continues until the array is sorted.
Selection Sort traverses a range of n principles n−1.periods. This is due to the fact that the last value needs to be in the proper location when the algorithm has sorted all other values except for it.
Every value in the array is compared the first time the algorithm goes through it to determine which is the lowest.
When the algorithm cycles over the array a second time, all values are compared to determine which is the lowest, with the exception of the first value.
And in this way the unsorted part of the array becomes shorter and shorter until the sorting is done. So on average, n/2 elements are considered when the algorithm goes through the array finding the lowest value and moving it to the front of the array.
Not only are all the comparisons required, but n swaps are also required.
We can now begin to determine how many operations the Selection Sort algorithm will require:
===formula===
When looking at the run time for algorithms, we look at very large data sets, meaning n is a very big number. And for a very big number n, the term n/2 2becomes so much bigger than the term n/2that we can approximate by simply removing that second term n/2.
===formula==
When we express the Selection Sort algorithm’s temporal complexity in Big O notation, we obtain:
===formula===
Additionally, the Selection Sort algorithm’s time complexity is shown in the following graph:
As you can see, the run time is the same as for Bubble Sort: as the array size increases, the run time grows exponentially.
Selection Sort Simulation
Run the simulation for different number of values in an array, and see how the number of operations Selection Sort needs on an array of n elements is O(n2):
===image===
The biggest distinction between Selection Sort (O) and Bubble sort that we can observe in this simulation is that the best and worst cases are nearly identical.n2.)), although the best case runtime for Bubble Sort is merely O(n)..
The number of swaps is the primary factor separating the best case from the worst scenario for Selection Sort. The array is already sorted, thus in the best situation, Selection Sort doesn’t need to swap any values. In the worst situation, Selection Sort will need to do as many swaps as there are values in the array because the array has already been sorted, albeit in the incorrect order.
