how to implement a descending selection sort in java?

Question

i want to implement a selection sort method that takes an array of ints and sorts it in a descending order. however, the trick is to keep the original selection sort method unchanged but instead using simple arithmetic operations and without adding extra loops to swap the elements after the array finished sorting. this is my code and the idea is to store the position of the maximum value and the minimum value in local variables and swap them with the corresponding position after the inner loop finishes iteration. i even tried using a only one variable to find the lowest value and put it at the end of the array but i failed and i am getting the wrong results and i need help spotting the error. here is my code

public static void newSortMethod(int[]a){
    for(int i = 0; i < a.length-1; i++){
        int maxPosition=i;
        int minPosition=i;
        for(int j = i+1; j < a.length; j++){
            if(a[j] < a[minPosition]){
                minPosition = j;
            }
            if(a[j] > a[maxPosition]){
                maxPosition = j;
            }
        }
        swap(a,maxPosition,i);
        swap(a,minPosition,a.length-i-1);
    }
    System.out.println();
}

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

public static void main(String[] args) {
    int[] a = {2,6,3,9,5,4,8,7,0,13,-3,1};
    newSortMethod(a);
}

here is the output of the program so far -3 8 2 9 13 5 4 6 3 1 7 0

Why are you comparing a[j] < a[i]? Shouldn't you be doing a[j] < a[minPosition] ? — jbx
– jbx, Commented Sep 17, 2018 at 18:43

Leo Aso · Accepted Answer · 2018-09-17 18:50:07Z

2

Your original algorithm is wrong. Firstly, the if blocks should compare to minPosition and maxPosition, not i. Secondly, if you are selecting both minimum and maximum, then your inner for loop should stop at a.length - i, not a.length (since the top i elements are also sorted). Doing both gives you this as the ascending order algorithm.

public static void newSortMethod(int[]a){
    for(int i = 0; i < a.length; i++){
        int maxPosition=i;
        int minPosition=i;
        for(int j = i+1; j < a.length - i; j++){
            if(a[j] < a[minPosition]){
                minPosition = j;
            }
            if(a[j] > a[maxPosition]){
                maxPosition = j;
            }
        }
        swap(a,maxPosition,i);
        swap(a,minPosition,a.length-i-1);
    }
}

To switch to descending order, simply add one line.

public static void newSortMethod(int[]a){
    for(int i = 0; i < a.length; i++){
        int maxPosition=i;
        int minPosition=i;
        for(int j = i+1; j < a.length - i; j++){
            if(a[j] < a[minPosition]){
                minPosition = j;
            }
            if(a[j] > a[maxPosition]){
                maxPosition = j;
            }
        }
        swap(a,minPosition,maxPosition); // <-- this line
        swap(a,maxPosition,i);
        swap(a,minPosition,a.length-i-1);
    }
}

answered Sep 17, 2018 at 18:50

Leo Aso

12.6k4 gold badges28 silver badges52 bronze badges

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

3 Comments

Red Eyez Over a year ago

i tried this code with input {1,2,4,3,5,0} and its swapping the middle value twice making an error on in the middle. i got those output 5 4 2 3 1 0

Red Eyez Over a year ago

i put an if statement before the first swap: if(i < a.length/2-1). it is working better now

Hardik Masalawala Over a year ago

@RedEyez, How many swap function line need to include in if condition(1st swap only, 1st and 2nd, all three)?

Gregory Gan · Accepted Answer · 2018-09-17 19:18:10Z

Errors

First off, let’s look for problems in your code. There’s a few, which happens a lot in programming.

Your code is still trying to sort ascending with swap(a,minPosition,i), and then trying to put the maximum value at the end, which isn’t what you want: you want to put maximum values at the beginning.
Your n is never modified, so you’ll keep printing 0.

Sample solution

Now let’s see something that works. I’m not totally sure what your ascending selection sort looked like, but I imagine it should be something like this:

public static void ascendingSortMethod(int[]a){
    int n = 0; // this is only to count how many times the swap method was called
    for(int i = 0; i < a.length-1; i++){
        int minPosition = i;
        for(int j = i+1; j < a.length; j++){
            if(a[j] < a[minPosition]){
                minPosition = j;
            }
        }
        if(minPosition != i){ // check whether swap is necessary
            swap(a,minPosition,i);
            n ++;
        }
    }
    System.out.println(n);
}

To make it sort in descending order, just switch the comparison operator (and possibly the minPosition identifier for clarity).

public static void newSortMethod(int[]a){
    int n = 0; // this is only to count how many times the swap method was called
    for(int i = 0; i < a.length-1; i++){
        int maxPosition = i;
        for(int j = i+1; j < a.length; j++){
            if(a[j] > a[maxPosition]){ // switched comparison operator
                maxPosition = j;
            }
        }
        if(maxPosition != i){ // check whether swap is necessary
            swap(a,maxPosition,i);
            n ++;
        }
    }
    System.out.println(n);
}

Collectives™ on Stack Overflow

how to implement a descending selection sort in java?

2 Answers 2

3 Comments

Errors

Sample solution

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Errors

Sample solution

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related