How to efficiently sort a Multidimensional Arrray

148
April 22, 2019, at 10:10 PM

I was given a task to sort multidimensional array into ascending order without using the pre-made functions in the Array class (such as .sort).

I've tried asking some of my friends for ideas... Many of them turns the array into a single-dimensional array, sort it the way you would sort a single-dimensional array and then turns it back into a multidimensional array.

I'm just curious to know if there'd be any other ways to do this without having to go through such trouble.

Answer 1

here is a full exemple you can tri

import java.util.Arrays;
import java.util.Comparator;
public class PartNumberQuantityDetailer {
// initialize a two dimensional array
static Integer[][] itemIdAndQty = new Integer[5][2];
public static void main(String[] args) {
    // initialize array values
    itemIdAndQty[0][0] = 1234;
    itemIdAndQty[0][1] = 46;
    itemIdAndQty[1][0] = 5443;
    itemIdAndQty[1][1] = 564;
    itemIdAndQty[2][0] = 362;
    itemIdAndQty[2][1] = 24;
    itemIdAndQty[3][0] = 6742;
    itemIdAndQty[3][1] = 825;
    itemIdAndQty[4][0] = 347;
    itemIdAndQty[4][1] = 549;
    System.out.println("Before sorting");
    // show the contents of array
    displayArray();
    // sort the array on item id(first column)
    Arrays.sort(itemIdAndQty, new Comparator<Integer[]>() {
        @Override
                    //arguments to this method represent the arrays to be sorted   
        public int compare(Integer[] o1, Integer[] o2) {
                            //get the item ids which are at index 0 of the array
            Integer itemIdOne = o1[0];
            Integer itemIdTwo = o2[0];
            // sort on item id
            return itemIdOne.compareTo(itemIdTwo);
        }
    });
    // display array after sort
    System.out.println("After sorting on item id in ascending order");
    displayArray();
    // sort array on quantity(second column)
    Arrays.sort(itemIdAndQty, new Comparator<Integer[]>() {
        @Override
        public int compare(Integer[] o1, Integer[] o2) {
            Integer quantityOne = o1[1];
            Integer quantityTwo = o2[1];
            // reverse sort on quantity
            return quantityOne.compareTo(quantityTwo);
        }
    });
    // display array after sort
    System.out.println("After sorting on quantity in ascending order");
    displayArray();
}
private static void displayArray() {
    System.out.println("-------------------------------------");
    System.out.println("Item id\t\tQuantity");
    for (int i = 0; i < itemIdAndQty.length; i++) {
        Integer[] itemRecord = itemIdAndQty[i];
        System.out.println(itemRecord[0] + "\t\t" + itemRecord[1]);
    }
    System.out.println("-------------------------------------");
}

}]

Answer 2

sort multidimensional array into ascending order:

You can sort multi-d array row-wise or column -wise.

If you don't want to flatten the array that is convert it into 1-d then that mean you have to go through each row or column depending on your choice and apply quick-sort(better performance for small data set if pivot is chosen optimally) or merge-sort.

So you can do both in (considering avg. case) O(nlogn) and say there are n rown or n columns the time complexity will be O(n^2(logn)).

Now above the assumption is that you want to sort either row-wise or column-wise. If you want to achieve the both(row and column) then it's better if you convert the array to 1-d and then apply sort and then convert it back. Otherwise following above approach the time complexity can go O(n^2(logn)) but in the other case it will be O((n+m)log(n+m)) where n amd m are no. of rows and columns in array plus the O(n+m) space complexity.

In my opinion having a bit of space complexity so that you can bring down the run-time is preferable.

READ ALSO
How to pass through form filling with web-scratching?

How to pass through form filling with web-scratching?

How to pass through website login form and see HTML code of any related webpages on website

147
Accordion Scroll to

Accordion Scroll to

I am trying to add an scrollTo command to the following accordion code

125
SQLiteOpenHelper - Cannot access disposed object

SQLiteOpenHelper - Cannot access disposed object

I have a my SQLiteOpenHelper class, which is written as a singletonI should note that I am not doing this in Java, I am using Xamarin

122
In Javascript IF-ELSE, IF Statement is not working

In Javascript IF-ELSE, IF Statement is not working

I am trying to work on verifying OTPHere I have two components that are:

15