0

I have a basic insertion sort function which takes 2D String Array and an index value as argument, then sorts that arrays according to that indexes, which is below:

public static void insertionSort(String[][] arr,int featureindex) {
        int j;
        double key;
        int n = arr.length;
        for (int i = 2; i < n; i++){
            key = Double.parseDouble(arr[i][featureindex]);
            String[] keyRow = arr[i];
            j = i - 1;
            while ((j > 0) && (Double.parseDouble(arr[j][featureindex]) > key)){
                arr[j+1] = arr[j];
                j = j - 1;
            }
            arr[j+1] = keyRow;
        }
    }

I know that insertion sort is slower than merge sort or quicksort, but i have to compare different sorting algorithms (did mergesort and quicksort) and thought that insertion would be better than bubble and selection sort,however, it came out slower than i expected. It sorts 50 000 arrays in ~140 seconds and 100 000 arrays in more than 700 seconds. I am just trying to optimize it as much as possible so that it has to also process 250 000 arrays. My Data looks like that:(4 arrays for example):

String[][] testArr = {
                {"Flow ID"," Source IP","Source Port","Destination IP","Destination Port","Protocol","Timestamp","Flow Duration"," Total Fwd Packets","Total Backward Packets"}
                ,{"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","12"}
               ,{"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","12"}
               ,{"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","987"}
               ,{"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","6"}
                };

here i have 10 elements in each subarray however, in actual one, it is lets say 250000 x 84 array.

is there any way to improve this?

James Z
  • 12,209
  • 10
  • 24
  • 44
Habil Ganbarli
  • 213
  • 2
  • 7
  • 14
  • What exactly is your question? Why your performance is better than expected or how to improve the performance of your function? But anyway - without seeing any code I'd guess that one of your issues is the measurement itself. Do you know about https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java? – Marvin Mar 11 '18 at 20:04
  • It also might help to give us an [MCVE,](https://stackoverflow.com/help/mcve) including a routine to generate data so that we can all measure the same thing. Trying to guess at your data might be an issue. (If you use `Random` give it a fixed seed value so we all use the same random sequence.) – markspace Mar 11 '18 at 20:08
  • 1
    Also: calling `parseDouble()` as the condition of the inner loop is likely to be chewing up a lot of cycles. – markspace Mar 11 '18 at 20:11
  • I edited the exemplified data there markspace and thanks for your feedback .And Marvin, my question is is there any way or hint i can improve it? Or is it just normal for insertion sort that it usually does not work better than that?I have to make it sort arrays in minial time and currently it seems problematic. – Habil Ganbarli Mar 11 '18 at 20:21

0 Answers0