CODEWITHSUNDEEP
javamultidimensional-arraymergesort
Habil Ganbarli
Habil Ganbarli

Reputation: 223

MergeSort in 2D Array Java

I have function for which should sort 2D String array according to some feature index. Here is my 2D array of 4 elements (4 x 10).

String[][] testArr = {
                {"192.168.1.101-67.212.184.66-2156-80-6","192.168.1.101","2156","67.212.184.66","80","6","13/06/2010 06:01:11","2328040","2","0"}
               ,{"192.168.1.101-67.212.184.66-2159-80-6","192.168.1.101","2159","67.212.184.66","80","6","13/06/2010 06:01:11","2328006","2","0"}
               ,{"192.168.2.106-192.168.2.113-3709-139-6","192.168.2.106","3709","192.168.2.113","139","6","13/06/2010 06:01:16","7917","10","9"}
               ,{"192.168.5.122-64.12.90.98-59707-25-6","192.168.5.122","59707","64.12.90.98","25","6","13/06/2010 06:01:25","113992","6","3"}
                };

I want to sort these elements according to lets say their 7th index, which is (2328040,2328006,7917,113992) in each element respectively. Here is the function I wrote for it:

// ************MERGE SORT***************************
public static void mergeSort(String[][] arr,int featureIndex){
        mergeSort(arr,new String [arr.length][84],0,arr.length-1,featureIndex);

}
// MERGE SORT HELPER FUNCTION
public static void mergeSort(String[][] arr,String [][] temp,int leftStart,int rightEnd,int featureIndex){
        if(leftStart >= rightEnd){
            return;
        }
        int mid = (leftStart + rightEnd)/2;
        mergeSort(arr,temp,leftStart, mid,featureIndex);
        mergeSort(arr,temp,mid + 1, rightEnd,featureIndex);
        mergeHalves(arr,temp,leftStart,rightEnd,featureIndex);
}
// Merge 2 Halves
public static void mergeHalves(String[][] arr,String[][] temp,int leftStart,int rightEnd,int featureIndex){
        int leftEnd = (rightEnd + leftStart)/2;
        int rightStart = leftEnd + 1;
        int size = rightEnd - leftStart + 1;

        int left = leftStart;
        int right = rightStart;
        int index = leftStart;


        while(left <= leftEnd && right <= rightEnd){
            if(Double.parseDouble(arr[left][featureIndex]) <= Double.parseDouble(arr[right][featureIndex])){
                temp[index][featureIndex] = arr[left][featureIndex];
                left++;
            }else{
                temp[index][featureIndex] = arr[right][featureIndex];
                right++;
            }
                index++;
        }
        // Copy the arrays
        System.arraycopy(arr, left, temp, index, leftEnd - left + 1);
        System.arraycopy(arr, right, temp, index, rightEnd - right + 1);
        System.arraycopy(temp, leftStart, arr, leftStart, size);

}

When I run the program it prints out 7917 7917 7917 113992 respectively in each element. How can I fix this?

Upvotes: 1

Views: 5909

Answers (2)

Jose da Silva Gomes
Jose da Silva Gomes

Reputation: 3974

Your merge function has some problems, you could simplify the function to

public static void mergeHalves(String[][] array,
                               String[][] aux,
                               int start, int middle, 
                               int end, 
                               int index) {

    if (start >= end) return;

    int ls = start, le = middle, rs = middle + 1, re = end, size = end - start + 1;

    for (int i = 0; i < size; i++) {
        if (rs > re) {
            aux[i] = array[ls++];
        } else if (ls > le) {
            aux[i] = array[rs++];
        } else if (Double.parseDouble(array[ls][index]) 
                <= Double.parseDouble(array[rs][index])) {
            aux[i] = array[ls++];
        } else {
            aux[i] = array[rs++];
        }
    }

    System.arraycopy(aux, 0, array, start, size);

}

Using this approach (merge sort of a array of arrays), you would need to deal with the types in the array, because in this case you cannot use parseDouble the columns 0, 1, 3 and 6. You could use a Comparator of string Comparator<String> as variable in mergeHalves() replacing the comparation in the else if with comparator.compare(array[ls][index], array[rs][index]) <= 0. Then defining and passing the comparator acording to the type of data.

Upvotes: 2

Jan Larsen
Jan Larsen

Reputation: 871

Put the arrays in an ArrayList instead of the outer array. Arrays.asList() can be used for that.

Define a Comparator that takes two arrays and sorts them using the 7th element

Use Collections.sort(List, Comparator) to sort it for you. It uses MergeSort.

You can never code anything as good as the standard libraries.

Upvotes: 2

Related Questions