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.