Java sort by selection: which is better in regards to readability and efficiency?

Question

Which algorithm do you think is better in regards to readability and efficiency?

selection():

public static int[] selection(int[] tab) {
 int minor;
 int aux;
 for (int i=0; i<tab.length-1; i++) {
 minor = tab[i];
 for (int j=i+1; j<=tab.length-1; j++) {
 if (tab[j] < minor) {
 aux = tab[j];
 tab[j] = minor;
 minor = aux;
 }
 }
 tab[i] = minor;
 }
 return tab;
}

otherSelection():

public static int[] otherSelection(int A[]) {
 int i, j, minor, pos, tmp;
 for (i = 0; i < A.length - 1; i++) {
 minor = A[i]; 
 pos = i;
 for (j = i + 1; j < A.length; j++){
 if (A[j] < minor) {
 minor = A[j]; 
 pos = j;
 }
 }
 if (pos != i){
 tmp = A[i];
 A[i] = A[pos];
 A[pos] = tmp;
 }
 }
 return A;
}

• MadProgrammer: I think you'll have better luck with this question Programmers Exchange
• But I'm Not A Wrapper Class: Better in what sense? Readability? Efficiency? Maintainability? etc
• Víctor: Mainly in readibility and efficency. Which one do you like the most? Thank you.
• Martin Schröder: May I introduce a feature that's around since Java 1.5 (or nearly a decade): enhanced for each loops. And please learn about Collections (introduced in Java 1.2). And please read Clean Code.

Answer 1

Readability:

The first one is far more readable because it can be translated at so:

selection(tab) 
 for each value of tab: i = (0->size-1) 
 minor = tab[i]
 for each value of tab: j = (i->size-1) 
 if (tab[j] < minor) 
 swap(minor, tab[j])
 tab[i] = minor;
 return tab;

This is very simple and symmetric. The otherSelection is a bit more difficult to read because it tracks a pos. This is a uncommon way to do this sort (not necessarily bad). Then it does the swap post inner loop. This was personally more difficult for me to read. The first wins here.

Time Efficiency:

Both run \$O(n^2)\$. However, otherSelection does only swap once per n-iteration. This actually is more efficient to do.

Space Efficiency:

selection only needs 4 int variables where as otherSelection needs 5. It's a bit more space efficient to use selection. As user @200_success mentioned, the space efficiency is the same at worse case since both are constant space \$O(1)\$. This isn't counting the input space (which you shouldn't really anyways).

Final verdict:

selection is a better option than otherSelection as far as readability. However, otherSelection is better for efficiency. This is a better variant of otherSelection which is just as good when it comes to space efficiency:

public static void selectionSort2(int[] x) {
 for (int i=0; i<x.length-1; i++) {
 int minIndex = i; // Index of smallest remaining value.
 for (int j=i+1; j<x.length; j++) {
 if (x[minIndex] > x[j]) {
 minIndex = j; // Remember index of new minimum
 }
 }
 if (minIndex != i) { 
 //... Exchange current element with smallest remaining.
 int temp = x[i];
 x[i] = x[minIndex];
 x[minIndex] = temp;
 }
 }
}

If you care for efficiency, this is the better selection sort option. You could also do a bit-swap for when swapping the variables.

Final notes: Since this is Java, you don't need to do the return statement at the end.

• 200_success: For all practical purposes, space efficiency is a tie.
• But I'm Not A Wrapper Class: @200_success Yes. In both cases, the worse case space efficiency is constant space. I was just nitpicking at that point.

Answer 2

In terms of readability, I would go for the first one selection. You would like to do everything cleanly inside 2 nested for clarity. Both are \$ O \left( n^{2} \right) \$.

Answer 3

First one is definitely better. More variables you have, the harder it is to follow them. That said, I'd suggest applying some rules:

1. A <= comparison is very unusual and triggers an unnecessary attention

2. Declare a variable in the scope it it used in

3. Recognize important algorithms and factor them out

4. A loop usually represent an important algorithm

Let's apply the first rule:

public static int[] selection(int[] tab) {
 int minor;
 int aux;
 for (int i=0; i<tab.length-1; i++) {
 minor = tab[i];
 for (int j=i+1; j<tab.length; j++) {
 if (tab[j] < minor) {
 aux = tab[j];
 tab[j] = minor;
 minor = aux;
 }
 }
 tab[i] = minor;
 }
 return tab;
}

Then the second:

public static int[] selection(int[] tab) {
 for (int i=0; i<tab.length-1; i++) {
 int minor = tab[i];
 for (int j=i+1; j<tab.length; j++) {
 if (tab[j] < minor) {
 int aux = tab[j];
 tab[j] = minor;
 minor = aux;
 }
 }
 tab[i] = minor;
 }
 return tab;
}

The code in if clause is one of the most fundamental algorithms, namely swap. I am afraid Java doesn't support swapping the way C++ programmers use; we just can't pass an integer to a function to have it modified. In this particular case Java "deficiency" pushes us to the right direction: what we actually want is to swap values in array - no need for minor at all! Here is an application of a third rule (with swap provided separately):

public static int[] selection(int[] tab) {
 for (int i=0; i<tab.length-1; i++) {
 for (int j=i+1; j<tab.length; j++) {
 if (tab[j] < tab[i]) {
 swap(tab, i, j);
 }
 }
 }
 return tab;
}

Now we may focus on the fourth rule: what does the inner loop represent? A swap which finally settle the value of tab[i] is the smallest tab[j] in the range. This would be my final code (index_of_min provided separately):

public static int[] selection(int[] tab) {
 for (int i=0; i<tab.length-1; i++) {
 int index_of_min = index_of_minimum(tab, i + 1, tab.length);
 if (tab[index_of_min] < tab[i]) {
 swap(tab, i, index_of_min)
 }
 }
 return tab;
}

BTW, now an opportunistic optimization is obvious (I am not sure I'd go for it but anyway):

public static int[] selection(int[] tab) {
 for (int i=0; i<tab.length-1; i++) {
 int index_of_min = index_of_minimum(tab, i + 1, tab.length);
 if (tab[index_of_min] >= tab[i]) {
 ++i;
 }
 swap(tab, i, index_of_min);
 }
 return tab;
}

Answer 4

Readability

None of them. Your method and variable names do not express the intent of your code. If you want readability, your code should "read like well-written prose".