Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 2 down vote favorite

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:)

share|improve this question

2 Answers

up vote 1 down vote accepted

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;
  }
}
share|improve this answer
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 – user524156 Dec 5 '10 at 17:09
up vote 1 down vote

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

share|improve this answer
thats for the answer Adam, I will run a speed test on this now – user524156 Dec 5 '10 at 16:58
bubble sort to sort 100,000 elements = 50.9 seconds, this method = 1.31seconds:) – user524156 Dec 5 '10 at 17:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.