Sorting an integer array in java, using selection sort. Cannot find my error

305 views Asked by At

I'm trying to learn code by making 'easy' exercises. I am trying to make a search algorithm using selection sort. When I follow the code inside my head it makes perfect sense, but when I run it, it does not order anything. For the array I am using an integer only array, it consist of random numbers and is of random length.

int currentMin;
    int currentMinIndex = 0;
    int temp;
    for(int i=0;i<array.length-1;i++){
        currentMin = array[i]; 
        for(int j=i+1;j<array.length-1;j++){
            if(array[j]<currentMin){
                currentMinIndex = j; 
                currentMin = array[j];
            }
        }
        temp = array[currentMinIndex]; //I am aware this could be currentMin 
        array[currentMinIndex] = array[i];
        array[i] = temp;
    }

I hope someone will spot my mistake and tell me. (If you have other 'easy' exercises I could do, creativity is appreciated, however this post must stay on topic)

Edit: I just noticed that in some weird way when the array is of large length it sorts but the last one. (array length vary because they are random)

3

There are 3 answers

0
Elliott Frisch On BEST ANSWER

You need to update currentMinIndex to i when you set currentMin, and your inner loop should be to array.length.

currentMin = array[i]; 
currentMinIndex = i;
for(int j=i+1;j<array.length;j++){

You could further simplify this by moving your declarations into the loop and removing temp (as you have currentMin) like

for (int i = 0; i < array.length - 1; i++) {
    int currentMin = array[i];
    int currentMinIndex = i;
    for (int j = i + 1; j < array.length; j++) {
        if (array[j] < currentMin) {
            currentMinIndex = j;
            currentMin = array[j];
        }
    }
    array[currentMinIndex] = array[i];
    array[i] = currentMin;
}
0
Abhishek Patel On

Both your loops are skipping the last element. Consider using <= instead of < in your loops conditions to consider the last element as well.

0
leeyuiwah On

There were two problems

  1. You forgot to reset currentMinIndex
  2. The boundary condition in the inner for loop was not right

Here is a modified version of your code:

public class SelectionSort {

    public static void main(String[] args) {
        int currentMin;
        int currentMinIndex = 0;
        int temp;
        int[] array = {9, 1, 3, 2, 4, 7};
        for(int i=0;i<array.length-1;i++){  
            currentMin = array[i]; 
            currentMinIndex = i;                    // Problem #1
            for(int j=i+1;j<=array.length-1;j++){   // Problem #2
                if(array[j]<currentMin){
                    currentMinIndex = j; 
                    currentMin = array[j];
                }
            }
            temp = array[currentMinIndex]; //I am aware this could be currentMin 
            array[currentMinIndex] = array[i];
            array[i] = temp;
        }

        StringBuilder sb = new StringBuilder();
        sb.append("[");
        String comma = "";      // first time special
        for (int i=0; i<array.length; i++) {
            sb.append(comma + array[i]);
            comma = ", ";       // second time and onwards
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

The output of this program is

[1, 2, 3, 4, 7, 9]