Sorting 2D array using selection sort

Question

I've used the following code -

x[][] is the array to be sorted

    void sort() {
    int max1, max2, s;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < column; j++) {
            max1 = i;
            max2 = j;
            for (int k = i; k < row; k++) {
                if (k == i) {   // need to improve this part
                    for (int l = j; l < column; l++) {
                        if (x[k][l] > x[max1][max2]) {
                            max1 = k;
                            max2 = l;
                        }
                    }
                } else {
                    for (int l = 0; l < column; l++) {
                        if (x[k][l] > x[max1][max2]) {
                            max1 = k;
                            max2 = l;
                        }
                    }
                }
            }
            s = x[max1][max2];
            x[max1][max2] = x[i][j];
            x[i][j] = s;
        }
    }
}

I want to remove the if else statement or is this another way to do it using selection sort?

(I know there are simpler ways to do this but I'm trying to do it with selection sort)

When you say "I want to remove the if else statement" do you mean improve? — RostSunshine
– RostSunshine, Commented Jun 13, 2017 at 15:56
Can you give us more information. I am trying to parse through the code and I don't understand what the variables r and c are. Can you give me the rest of the code. Also you have lots of nested for loops which is really really bad for efficiency. — RostSunshine
– RostSunshine, Commented Jun 13, 2017 at 16:01
I am working on a solution, sorry for wait, I don't have java installed on this comp and can't currently so having to debug and logic myself. — RostSunshine
– RostSunshine, Commented Jun 13, 2017 at 16:26

tucuxi · Accepted Answer · 2017-06-13 16:35:47Z

I really do not like how you name your variables. I suggest using r, c as prefixes for row and column, v for value, and then using Outer and Inner as suffixes for the two loops over the array, and Max for the maximum.

Using vMax increases the memory locality of your algorithm - by avoiding lookups to distant parts of memory, it should execute slightly faster when dealing with large arrays. Not that select-sort is ever going to be competitive when compared to, say, quickSort: asymptotic complexity will remain horrible.

This makes everything easier to read:

for (int rOuter = 0; rOuter < rows; rOuter++) {
    for (int cOuter = 0; cOuter < cols; cOuter++) {
        // find max value, and swap with rOuter, cOuter            
        int rMax = rOuter;
        int cMax = cOuter;
        int vMax = x[rOuter][cOuter];
        // finish the row current row
        for (int cInner = cOuter+1; cInner < cols; cInner++) {
            if (x[rOuter][cInner] > vMax) {
                rMax = rOuter; 
                cMax = cInner; 
                vMax = x[rOuter][cInner];
            }
        }
        // evaluate remaining rows
        for (int rInner = rOuter+1; rInner < rows; rInner++) {
            for (int cInner = 0; cInner < cols; cInner++) {
                if (x[rInner][cInner] > vMax) {
                   rMax = rInner; 
                   cMax = cInner; 
                   vMax = x[rInner][cInner];
                }
            }
        }            
        // swap. No aux needed, as vMax contains value of max
        x[rMax][cMax] = x[rOuter][cOuter];
        x[rOuter][cOuter] = vMax;
    }
 }

Note that I have removed the innermost conditional: it should be executed once, and only once, to finish the current row before evaluating all remaining rows.

Also note - I have not tested this code. It looks correct, but treat it with caution.

RostSunshine · Accepted Answer · 2017-06-13 20:08:10Z

0

Like I mentioned I don't have the medium to test this currently, but I believe this should work. If not let me know and I will alter it accordingly.

Here is my solution:

void sort() {
 int max1, max2, count, minValue, rowHold, colHold;
 int[][] tempArr = new int[row][column]; 
 while(count != (row*column)) 
 {
    for (int i = 0; i < row; i++) 
    {
            for (int j = 0; j < column; j++) 
        {
                max1 = i;
                max2 = j;
            if(minValue>x[i][j] && x[i][j] != tempArry[i][j])
            {
                minvalue= x[i][j];
            }



        }

    }

    tempArr[rowHold][colHold] = minVlaue;
    if(colHold<column)
    {
    colHold++;
    }
    else if(colHold=column)
    {
        colHold = 0;
        rowHold++;
    }
    count++;
}   
x = tempArry;

}

This solution preforms a selection sort and many times more efficiently than your current solution. The problem with your current solution is it has way too many nested loops. Nested loops create huge problems in terms of efficiency so you want to minimize the use and depth of them.

Hope this works, comment on this if it does not and I will fix it! Also any questions on what I did and I will comment and explain what I did.

edited Jun 13, 2017 at 20:08

answered Jun 13, 2017 at 16:37

RostSunshine

2461 gold badge4 silver badges14 bronze badges

7 Comments

tucuxi Over a year ago

I would be very interested in seeing whether your code is "many times faster" than OP's or not. I am ready to bet that, once you fix the bugs, it will take around the same time: all correct selection sorts should perform around the same. One obvious bug is that you increment rowHold and colHold at each iteration - leading to an early ArrayIndexOutOfBounds exception.

RostSunshine Over a year ago

@tucuxi yes they do, but you can over complicate them servery which I would argue the OP did with having 4 for loops nested creates chaos where as two is much less even inside a while loop. He parsed through the array twice and with 2D arrays this is extremely inefficient.

tucuxi Over a year ago

It is still not "many times" faster than OP's code; the outer and inner loops are executed row*column times, just as in OP's (or my) case, but your code is harder to read than OP's. Also, you are sorting ascending, but OP was sorting descending.

RostSunshine Over a year ago

I mean N^4 is very different than N^2 so I would say that's many times. And if it is max then it is a switch of a name change and the "<" to a ">". So OP can choose which way. I did a selection sort, was not concerned with direction because this is easily switchable.

tucuxi Over a year ago

The number of lookups to sort an n-item array (n = rows x cols if 2-dimensional; n = depth x rows x cols if 3-dimensional) using select-sort is in the order of n^2 (one full outer loop, one partial inner loop). The number of "for" or "while" statements is not important - I can loop o(n!) times with a single while-loop. The important number is how many times I execute the innermost code. And that is n^2 in your code, OP's, and mine.

|

Collectives™ on Stack Overflow

Sorting 2D array using selection sort

2 Answers 2

Comments

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related