Selection sort implementation in Java

Question

Here's an implementation of selection sort, that sorts an array in ascending order.

Please let me know of any improvements/optimisations that can be done.

import java.util.List;
public class SelectionSort {
 public static void start(List<Integer> arrayToSort){
 for(int i = 0; i < arrayToSort.size(); i++) { // i = leftmost index of unsorted part of the array
 int minimumValue = i;
 for(int j = i; j < arrayToSort.size(); j++){
 if(arrayToSort.get(j) < arrayToSort.get(minimumValue)){
 minimumValue = j;
 }
 }
 swap(i, minimumValue, arrayToSort);
 }
 }
 private static void swap(int a, int b, List<Integer> arrayToSort){
 int temp = arrayToSort.get(a);
 arrayToSort.set(a, arrayToSort.get(b));
 arrayToSort.set(b, temp);
 }
}

Answer 1

I suggest you format

for(int i = 0; i < arrayToSort.size(); i++) { // i = leftmost index of unsorted part of the array

as

// i = leftmost index of unsorted part of the array
for(int i = 0; i < arrayToSort.size(); i++) {

swap takes arguments a, b and arrayToSort. These arguments could be more explanatory: swap doesn't sort anything and it doesn't take an array, and a and b don't say much.

It's canonical to use i and j as indices, so that would be more appropriate - although longer names wouldn't hurt either. The List argument would be better as items or similar. items is this-like, so put it first.

private static void swap(List<Integer> items, int i, int j) {
 int temp = items.get(i);
 items.set(i, items.get(j));
 items.set(j, temp);
}

You can also make this more like the OpenJDK implementation by using the return value from set:

private static void swap(List<Integer> items, int i, int j) {
 int temp = items.set(i, items.get(j));
 items.set(j, temp);
}

or even

private static void swap(List<Integer> items, int i, int j) {
 items.set(j, items.set(i, items.get(j)));
}

You could also make it generic.

private static <T> void swap(List<T> items, int i, int j) {
 items.set(j, items.set(i, items.get(j)));
}

Your sort is of course inefficient; you're using selection sort. However, you can at least make it a little faster. First neaten it up - including changing the name to something more descriptive. Note that minimumValue is not a value but an index - this should be fixed.

public static void sortInPlace(List<Integer> toSort){
 // i = leftmost index of unsorted part of the array
 for(int i = 0; i < toSort.size(); i++) {
 int minimumValue = i;
 for(int j = i; j < toSort.size(); j++) {
 if(toSort.get(j) < toSort.get(minimumValue)) {
 minimumValue = j;
 }
 }
 swap(toSort, i, minimumValue);
 }
}

You can change the inner loop to start at i + 1. You can also cache the value to halve the number of toSort.gets you make.

public static void sortInPlace(List<Integer> toSort){
 // i = leftmost index of unsorted part of the array
 for(int i = 0; i < toSort.size(); i++) {
 int minimumIndex = i;
 int minimumValue = toSort.get(i);
 for(int j = i + 1; j < toSort.size(); j++) {
 if(toSort.get(j) < minimumValue) {
 minimumIndex = j;
 minimumValue = toSort.get(j);
 }
 }
 swap(toSort, i, minimumIndex);
 }
}

This gives a noticeable speed improvement.

Frankly, though, if you want a reasonably fast integer selection sort, use an array. int[] is unboxed, which means that it's some 4x the speed. It's actually faster to copy into a temporary int[], sort and copy it back than to sort in a boxed List.

• Calculus5000: Oh wow. Thanks for this step-by-step feedback! I didn’t realise that there’s a 4x performance difference between arrays and ArraysLists. Do you know where I can find out more about this? Also, is there a significant performance difference between caching the value and using toSort.get()? I understand that it’s better to cache the value because you want to make the algorithm as fast as possible.
• Veedrac: "is there a significant performance difference between caching the value and using toSort.get()" → Indeed, it's about a factor of 2 for me. // int[] is faster because int is unboxed (just an integer) whereas Integer is boxed (a pointer to an int). Foo[] vs List<Foo> won't be as different since they both use Foo.