Sorting an array continuously

Question

I have a user give me a random array of objects, I want to do some error checking and basically I want the null objects to be at the end of the array, so that the middle of the array is made up of only non-null objects (sorting of the objects doesn't matter).

Here is what I have, it isn't working. Can anyone please help.

private void properArray(){
    int i = 0;
    int j;
    int cap = theHeap.length;
    for(; i < (cap-1); i++){
        if (theHeap[i] == null){
            j = i + 1;
            while(j < (cap-1)){
                if(theHeap[j] != null){
                    theHeap[i] = theHeap[j];
                    theHeap[j] = null;
                }
                j++;  
            }
        }
    } 
}

Lukas Eder · Accepted Answer · 2014-01-17 07:08:40Z

8

Here's a simpler way how you can sort such an array:

Arrays.sort(theHeap, new Comparator() {
  public int compare(Object o1, Object o2) {
    // nulls are "greater" than non-nulls
    if (o1 == null && o2 != null) return 1;
    // non-nulls are "smaller" than nulls
    if (o1 != null && o2 == null) return -1;
    // in all other comparisons, we don't care
    return 0;
  }
});

Or with Java 8:

Arrays.sort(theHeap, (o1, o2) -> (o1 == null && o2 != null) ?  1
                               : (o1 != null && o2 == null) ? -1
                               :                               0);

If you have Apache Commons Collections on your classpath, you can write this with even less code:

Arrays.sort(theHeap, new NullComparator());

As Ted mentions, this performs in O(n log n) and creates a clone of your array for sorting... It is thus not the fastest solution...

edited Jan 17, 2014 at 7:08

answered Mar 15, 2012 at 16:40

Lukas Eder

224k138 gold badges731 silver badges1.6k bronze badges

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

1 Comment

Ted Hopp Over a year ago

Why would this O(N log N) operation be more efficient? The task can be done in O(N).

Ted Hopp · Accepted Answer · 2012-03-15 19:16:44Z

3

There's no need to iterate twice through the array. If you don't care about the order of non-null objects (in particular, if they don't need to remain in the same relative order), you can do this very simply:

int end = theHeap.length;
for (int i = 0; i < end; ++i) {
    while (theHeap[i] == null && i < end) {
        --end;
        theHeap[i] = theHeap[end];
        theHeap[end] = null;
    }
}

Since each loop iteration (either outer or inner) reduces (end - i) by one, and the looping ends when they meet, this is an O(N) algorithm.

EDIT A revised version that avoids swapping nulls (slightly more efficient, perhaps):

int end = theHeap.length;
for (int i = 0; i < end; ++i) {
    if (theHeap[i] == null) {
         while (--end > i && theHeap[end] == null) {
             // loop
         }
         if (i < end) {
             theHeap[i] = theHeap[end];
             theHeap[end] = null;
         }
    }
}

EDIT 2 A much simpler version that also maintains the initial sort order of the non-null elements:

int next = 0;
for (int i = 0; i < theHeap.length; ++i) {
    if (theHeap[i] != null) {
        if (i > next) {
            theHeap[next] = theHeap[i];
            theHeap[i] = null;
        }
        ++next;
    }
}

edited Mar 15, 2012 at 19:16

answered Mar 15, 2012 at 16:40

Ted Hopp

235k48 gold badges412 silver badges533 bronze badges

3 Comments

Dilum Ranatunga Over a year ago

This will fail with input: ["x", null, "y", null]

Ted Hopp Over a year ago

@DilumRanatunga I revised the code, but how does the original fail? (I just ran it with your input and it worked fine.)

Lukas Eder Over a year ago

The third version is really a nice solution! Probably the optimal one for the OP

David Kroukamp · Accepted Answer · 2012-07-23 15:50:37Z

0

Try:

int j = array.length;
for (int i = 0; i < j; ++i) {
  if (array[--j] == null) {
    continue;
  }
  // array[j] is not null.
  if (array[i] == null) {
    array[i] = array[j];
    array[j] = null;
  }
}

edited Jul 23, 2012 at 15:50

David Kroukamp

36.4k13 gold badges85 silver badges138 bronze badges

answered Mar 15, 2012 at 16:42

Dilum Ranatunga

13.4k3 gold badges43 silver badges53 bronze badges

1 Comment

Ted Hopp Over a year ago

This fails with [null, "x", "y", null]

Collectives™ on Stack Overflow

Sorting an array continuously

3 Answers 3

1 Comment

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related