Why does this algorithm not sort the last index correctly?

Question

I am supposed to write a version of the selection sort algorithm that moves the smallest number to the front of the array while simultaneously moving the largest number to the end of the array. I understand that it is basically working from both ends in so there are two sorted sub arrays, however my code seems to misplace the last number in the array. My code:

public static void dualSelectionSort(int[]a) {
    for(int i=0; i<a.length-1;i++) {
        int min=i;
        int max=(a.length-1)-i;
        for (int j=i+1;j<a.length-i;j++) {
            if(a[j]<a[min]) {
                min=j;
            }
            if(a[j]>a[max]) {
                max=j;
            }
        }
        int temp1=a[min];
        int temp2=a[max];
        a[min]=a[i];
        a[max]=a[(a.length-1)-i];
        a[i]=temp1;
        a[(a.length-1)-i]=temp2;
    }
}

If given the input [5,4,3,2,1], it outputs [1,2,5,3,4] instead of [1,2,3,4,5]. What am I missing?

Answer 1

The problem is in the inner loop.

It is starting from i+1. So the code for comparing max is actually comparing a[1] to a[4].

you can change it as for (int j=i;j<a.length-i;j++)

Also as you can read in comment there can be a case where with the above change the code will still not work. This will happen because i == max and so the existing swap approach will not work. For example: assume array =[6,4,5],inner loop max =0,min=1.Existing swap will make it [4,6,6]. Hence,swap should be handled differently.

      if(i==max) {
            swap(a,max,a.length-1-i);
            swap(a,min,i);
        }else {
            swap(a,min,i);
            swap(a,max,(a.length-1)-i);
        }  

The complete code is as below:

public static void dualSelectionSort(int[]a) {
    for(int i=0; i<a.length-1;i++) {
        int min=i;
        int max=(a.length-1)-i;

        for (int j=i;j<a.length-i;j++) {
            if(a[j]<a[min]) {
                min=j;
            }
            if(a[j]>a[max]) {
                max=j;
            }
        }
        if(i==max) {
            swap(a,max,a.length-1-i);
            swap(a,min,i);
        }else {
            swap(a,min,i);
            swap(a,max,(a.length-1)-i);
        }       
    }
}

public static void swap(int[] a,int i,int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}