Selection Sort in Java

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s