sorting 2 dimensional java array

Question

I have implemented bubble sort to sort a two dimensional java long [][] but my god is it slow, I will be needing the fasted algorithm possible as i will be generating a array of the max heap size jvm will allow me,

So i think the best and fastest way would be to use the inbuild java Arrays.sort

I dont mind if it can only sort on column one as i can change my program to suit, I came across this but am not to familar with comaparator,

this will allow me to sort a dimensional array of integers, does anyone know how to change this to allow longs?, i did thinker around with it with no joy yet.

int d2 [][] = {{1,43},{26,98},{44,398},{11,34},{17,32}};

java.util.Arrays.sort(d2, new java.util.Comparator<int[]>() {
    public int compare(int[] a, int[] b) {
        return b[0] - a[0];
    }
});

i want to sort say

long d2L [][] = {{1,43},{26,98},{44,398},{11,34},{17,32}};

casting is not an option as the numbers a massive

Also if anyone thinks theres a faster method to sort im all ears:)

moinudin · Accepted Answer · 2010-12-05 17:02:22Z

2

This sorts based on all columns in O(NlogN), i.e. really fast:

import java.util.*;

class Compare2DArray implements Comparator {
  public int compare(Object a, Object b) {
    int aa[] = (int[]) a;
    int bb[] = (int[]) b;
    for (int i = 0; i < aa.length && i < bb.length; i++)
      if (aa[i] != bb[i])
        return aa[i] - bb[i];
    return aa.length - bb.length;
  }
}

class sort2d {
  public static void main(String args[]) {
    int d2 [][] = {{1,43},{26,98},{44,398},{11,34},{17,32}};
    Arrays.sort(d2, new Compare2DArray());
    for (int i = 0; i < d2.length; i++) {
      for (int j = 0; j < d2[i].length; j++)
        System.out.print(d2[i][j] + " ");
      System.out.println();
    }
  }
}

http://ideone.com/TjEOL

Or you could use generics to avoid casting:

class Compare2DArray implements Comparator<int[]> {
  public int compare(int a[], int b[]) {
    for (int i = 0; i < a.length && i < b.length; i++)
      if (a[i] != b[i])
        return a[i] - b[i];
    return a.length - b.length;
  }
}

edited Dec 5, 2010 at 17:02

answered Dec 5, 2010 at 16:56

moinudin

139k45 gold badges195 silver badges219 bronze badges

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

1 Comment

user524156 Over a year ago

thanks Marcog, i got my orignal question working with longs, i take it both are similar if you think this will run faster i may implement it

Adam Crume · Accepted Answer · 2010-12-05 16:51:53Z

1

Just use a compare method like this:

public int compare(long[] a, long[] b) {
    if(a[0] < b[0]) {
        return -1;
    } else if(a[0] > b[0]) {
        return 1;
    } else {
        return 0;
    }
}

I'd start out with the built-in Arrays.sort. That will run much, much faster than bubble sort. If it's still not fast enough, look at the algorithms here: http://en.wikipedia.org/wiki/Sorting_algorithms

answered Dec 5, 2010 at 16:51

Adam Crume

15.9k8 gold badges49 silver badges52 bronze badges

2 Comments

user524156 Over a year ago

thats for the answer Adam, I will run a speed test on this now

user524156 Over a year ago

bubble sort to sort 100,000 elements = 50.9 seconds, this method = 1.31seconds:)

Collectives™ on Stack Overflow

sorting 2 dimensional java array

2 Answers 2

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related