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.get
s 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
.