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?

Deepali Sinha · Accepted Answer · 2018-10-25 20:16:58Z

3

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

edited Oct 25, 2018 at 20:16

answered Oct 25, 2018 at 18:02

Deepali Sinha

442 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Eran Over a year ago

This is not enough. Trying the input [4, 5, 2, 1, 6, 10, 3, 9, 8, 0, 7] with your suggested fix yields [0, 1, 2, 3, 4, 6, 6, 7, 8, 9, 10].

Deepali Sinha Over a year ago

Thanks for pointing that out! yes you are correct.the previous solution was not enough and would not have handled the scenario if i==max

Eran · Accepted Answer · 2018-10-25 18:30:55Z

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:

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.
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.
The inner loop should iterate j from i+1 to (a.length-1)-i-1.

Collectives™ on Stack Overflow

Why does this algorithm not sort the last index correctly?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related