This is a Java implementation of a Selection Sort in Python from a previous post. I like the selection sort because it is simple, but it is not the most efficient. I’ll explore more in this post, and see how fast I can push this algorithm.
Let’s begin by implementing what was done in Python which uses two methods. The first method searches for the index of the item in the list with the smallest value:
The second method uses the first. It iterates through the specified items and extracts the smallest item one iteration at a time. This item is added to the results. This continues until there are no more items to extract:
This is the main method which demonstrates the sort:
The output is:
[2, 4, 10, 11, 13, 14, 23, 46, 53, 88]
Whilst I like the selection sort, I don’t like how the original list is mutated. If it is to be mutated, then I think it should contain the sorted items:
The updated main method:
Another alternative is to create a copy of the original list, and mutate that, then return the results as a new list. However, each of these operations adds overhead which may have a negative effect on memory and performance depending upon the size of the list.
Ignoring the mutating side-effect, let’s return to the original code. We can easily implement the first method more concisely:
That’s so succinct, we can actually remove that method, our final code looks like this:
The selection sort is a step above the bubble sort, but its performance is affected by the speed of removing an item from the original list. This should work faster if the source is a linked list:
Wow was I wrong! Here are the results, milliseconds per x items:
// LinkedList 1000: 187 2000: 1737 3000: 6739 4000: 16975 5000: 34866 // ArrayList 1000: 14 2000: 15 3000: 32 4000: 43 5000: 53 10000: 231 50000: 3176 100000: 12425 200000: 49532
Performance for both really deteriorates beyond these points for both lists.
Whilst Java’s ArrayList is impressively fast, to really test the performance of a LinkedList I need to modify the algorithm to work accordingly, for example using next(), and element() rather than indexing. Unfortunately Java’s LinkedList doesn’t support the next() operation. If I build a custom linked list in a future post, I’ll update these benchmarks.
Selection sort can process an ArrayList of 30,000 integer objects in under a second on a nearly 5 years old Intel Core i7-7700 @ 3.60GH. Increasing the comparison time, via string objects, resulted in 5 and a half seconds. Approximately 12,500 strings can be processed in a second:
If you need a simple sort, for under 10,000 items the selection sort is a good candidate.
Lastly, you can get impressive speeds by customizing this algorithm to your needs. For example, I get the following benchmarks by mutating an int array in place:
1000: 0 5000: 15 10000: 32 50000: 844 100000: 3204 200000: 12447 350000: 44495 500000: 90908
As expected, that’s much quicker than the previous examples. Here is the code:
I hope you enjoyed this brief tour of the selection sort.