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: 
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;
}

```
In each iteration of the outer loop, you start with the first index (i) as the initial minimum index and the last index (a.length-1-i) as the initial maximum index. Then you compare both of these indices to all the indices in the range i+1 to a.length-i-1. But if the first index (i) actually contain the max value, you never compare it to a[max], so a[max] will never contain the correct value in the end of the inner loop.

Here's a suggested fix:

```
public static void dualSelectionSort(int[]a) {
    for(int i = 0; i < a.length - i - 1; i++) {
        if (a[i] > a[(a.length - 1) - i]) {
            int temp = a[i];
            a[i] = a[(a.length - 1) - i];
            a[(a.length - 1) - i] = temp;
        }
        int min = i;
        int max = (a.length - 1) - i;
        for (int j = i + 1; j < (a.length -1 ) - 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;
    }
}

```

The three things I changed:

1. The outer loop can end much sooner than you end it - once `i >= a.length-i-1` - since in each iteration you find the minimum and maximum value, so you reduce your remaining unsorted array by 2.
2. When initializing the `min` and `max` indices, make sure `min` index actually contains a value smaller the `max` index. If `a[i] > a[(a.length-1)-i]`, swap them before setting `min` to `i` and `max` to `(a.length-1)-i`.
3. The inner loop should iterate `j` from `i+1` to `(a.length-1)-i-1`.