1
\$\begingroup\$

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);
    }
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 4, 2015 at 15:40
  • 1
    \$\begingroup\$ "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. \$\endgroup\$
    – Veedrac
    Apr 4, 2015 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.