I was playing around with this website (https://www.toptal.com/developers/sorting-algorithms/) and clicked on "Play Nearly Sorted". I noticed that the Selection Sort algorithm was considerably slower than the others. Can you please explain why this is so, and possibly point me to a link with more information on this. Thanks!
2 Answers
You'll notice selection sort actually just takes the same amount of steps regardless of the initial ordering of the data.
Selection sort can be described like this (pseudocode, assumes data is a list of length n and indices run from 1 to n inclusive)
for pass = 1 to n {
//at each pass, find the minimal item in the list (that we haven't already sorted)
indexMin = pass
for item = pass + 1 to n {
if data[item] < data[indexMin] {
indexMin = item
}
}
swap data[pass] and data[indexMin]
}
Like it's name suggests, it repeatedly (n times in fact) selects the smallest element, and then puts it in its proper position. This creates a sorted sublist at the beginning running from position 1 to position pass at each pass.
As you can see, selection sort has no capability of terminating early. It just takes a blind shotgun approach at sorting. It will always runs exactly n passes, even on an array that's already completely sorted.
Other algorithms often "know" when they're done sorting, and can terminate early. As Tim's comment says, selection sort is a brute force approach that will never run any faster than n^2
2 Comments
l57014
Thanks for the response. I have a followup question: I went ahead and made a program to test how long it would take for selection sort to finish sorting arrays of size 100000. I ran each test 10 times and got the averages. Here are the results: RD: 7486871ms(microseconds). NS: 20971045ms. Reversed: 8534483ms. FU: 7222612ms. Weirdly enough. the nearly sorted tests came out the slowest, while the others were of similar similar speeds. Does this have to do with the compiler or how the code is executed? Maybe I'm missing something.
CollinD
I'd suggest potentially asking another question since this is somewhat outside of the scope of this one. Most likely it's some caching or branch prediction quirk.
To fully understand the runtime of common sorting algorithms, it requires you to read through their pseudo code. In a "nearly sorted case," selection sort is the slowest because no matter what, its running time is always O(n^2), which runs in a polynomial time. Polynomial time is considered as the slowest among all the time complexity presented in the website you attached. Here is the code for selection sort:
public static void selectionSort(int [] A) {
for(int i = 0; i < A.length - 1; i++) {
int min = i;
for(int j = i + 1; j < A.length; j++){
if(A[j] < A[min])
min = j;
}
}
swap(A, i, min);
}
It always runs with these two "for" loops regardless the how much sorted the array A is. Regarding other algorithms, they are relatively "smarter" (faster) with the initial array A if it is somehow or nearly sorted. You can ask yourself in another way around; why insertion sort is so fast in a "nearly sorted array?" Hope this helps!
3 Comments
MBo
Your sentences about "polynomial time" are vague.
CollinD
Honestly, it's incorrect. Polynomial time is not considered to be the slowest time complexity. Consider factorial time, or exponential time. If you're referring only to the algorithms presented in OPs link, maybe specify that.
Bruce Lin
Yes, I was referring to the algorithm in the link. Thanks for specifying. @CollinD
O(n^2)sorting algorithm, much slower than merge and quick sort, and even slower than insertion sort.