Fast Algorithm in Java to Reverse an Array

Question

I have written code to reverse an array that has Time Complexity: O(n).

Is there a faster method?

My code:

 void reverseArray(int arr[], int start, int end){
        int temp;
        if(start >= end)
            return;
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        reverseArray(arr, start+1, end-1);   
    }

It might not be *faster*, but why not just convert it to a List and use Collections.reverse()? I usually trust that the people who wrote Java are smarter than I am, plus it makes the code more readable. — Kevin Workman, Jan 09 '14 at 14:46
I'm not sure if it will run faster, but why don't you just use a simple while loop with two indexes, one starting from the left and one from the right, instead of a recursive call to your function ? And don't reinvent the wheel, use `ArrayUtils.reverse(int[] arr)` from apache library. — user2336315, Jan 09 '14 at 14:47
@user2336315 - Couldn't agree more.. In recursion, the greater the size the higher the probablity of StackOverFlowError. — TheLostMind, Jan 09 '14 at 14:48
See http://stackoverflow.com/questions/2137755/how-do-i-reverse-an-int-array-in-java, http://stackoverflow.com/questions/9995432/reverse-array-order, and http://stackoverflow.com/questions/12678781/reversing-an-array-in-java. — Kevin Brock, Jan 09 '14 at 14:48

score 14 · Accepted Answer · answered Jan 09 '14 at 14:48

Literally reversing the elements in memory can't be done any faster than O(n). However, you could make a wrapper class that indexes the array reversed. So, in fact you don't reverse the array, but only access the elements backwards.

The code you have is O(n), but terrible because of the recursion. Make it flat and you will experience some benefit.

public static void reverseArray(int arr[], int start, int end)
{
    int len = end - start;
    if(len <= 0) return;

    int len2 = len >> 1;
    int temp;

    for (int i = 0; i < len2; ++i)
    {
        temp = arr[start + i];
        arr[start + i] = arr[end - i - 1];
        arr[end - i - 1] = temp;
    }
}

I like your suggestion of the wrapper class – JeremyP Jan 09 '14 at 14:55 — JeremyP, Jan 09 '14 at 14:55

score 4 · Answer 2 · answered Jan 09 '14 at 14:49

4

You are using recursion which is not as fast as a loop. You are still O(n) but with faster time to use a loop. Something like:

static void reverseArray(int arr[]){
   for (int start=0,end=arr.length-1;start<=end;start++,end--) {
      int temp = arr[start];
      arr[start] = arr[end];
      arr[end] = temp;
   }
}

For something like this you will be better off using methods provided in the Java libraries to do it though.

answered Jan 09 '14 at 14:49

Tim B

40,716
16
83
128

the main problem of the recursion is the memorie which is needed. – kai Jan 09 '14 at 14:50
1

It's both slower and uses more memory, and you are limited in iteration depth whereas a loop isn't. – Tim B Jan 09 '14 at 14:50
@kai - Tim is right... Recursion is slower because too many operations occur on the stack each time function is called recursively – TheLostMind Jan 09 '14 at 14:54
Be nice to know why I got a downvote :s – Tim B Jan 09 '14 at 14:55
@TheLostMind i know, i only want to point out that there is a memory problem too. thats not my downvote :) – kai Jan 09 '14 at 14:56
Maybe someone thinks the code is invalid or something. Double variables in loops aren't super-common. Try it here though: http://www.tryjava8.com/app/snippets/52ceb8c3e4b00bdc99e8ab59 – Tim B Jan 09 '14 at 14:57
@TimB - ya.. I think a comment should be made mandatory with a downvote :P – TheLostMind Jan 09 '14 at 14:57
@TheLostMind You would get a lot of garbage comments. Or comments saying they agree with what the previous downvoter said. – Cruncher Jan 09 '14 at 15:17
@Cruncher - Atleast we will get to know why we are getting downvotes.. Sometimes it so happens that people just keep dovnvoting and I don't understand why.. – TheLostMind Jan 09 '14 at 16:22
Perhaps it was downvoted because it's slower and the question specifically asks for faster (which is a problem with questions (i.e. many questions on a problem, each specifying required time and space complexities, as opposed to one question with answers covering all time and space complexities) I've been trying to find a viable solution to, but I don't think one exists in the current [so] format). – Bernhard Barker Jan 09 '14 at 16:33
The loop is faster than recursion. i.e. this answer is faster. It has the same O(n) and faster execution of each step. In fact it's almost identical to the answer that got +7 above except that he mentioned the idea of a wrapper class too. – Tim B Jan 09 '14 at 16:43

tomwesolowski · Answer 3 · 2017-04-19T16:18:54.397

4

You could use some intermediary function:

int rev(int i) {
    return arr.length - i - 1;
}
//...
arr[rev(i)] = 5; // reverse reference

edited Apr 19 '17 at 16:18

answered Jan 09 '14 at 14:51

tomwesolowski

956
1
11
27

nmargaritis · Answer 4 · 2014-01-09T17:41:13.687

2

If you use static arrays, since you will need to access every element once in order to reverse it, there is no smaller complexity than n.

However, if you use a double linked list, then by definiton you have access to the elements in both directions. From head to tail and from tail to head, because there are double pointers in the Node class used. Therefore, reverse is not even needed, but rather you iterate from tail to head when needed.

edited Jan 09 '14 at 17:41

answered Jan 09 '14 at 14:50

nmargaritis

859
7
21

You don't need to reverse an array either, you can just write a wrapper class that indexes the array in reverse (as per [this answer](http://stackoverflow.com/a/21023412/1711796)). – Bernhard Barker Jan 09 '14 at 16:16
@Dukeling Yes, however, the algorithm complexity for this is still O(n). On the other hand, when a double linked list is used, you do not have to make that step. Therefore the complexity for that is just O(1). You just access the elements from tail to head directly. – nmargaritis Jan 09 '14 at 16:24
No, you can assign the array to a member of the wrapper class (or it can start off in the wrapper class) and simply set a "reversed" flag in the wrapper class (indicating to the accessors and mutators that they should indexes the array in reverse), both in O(1). – Bernhard Barker Jan 09 '14 at 16:29
2

I mean something like [this](http://ideone.com/NrZHcc). – Bernhard Barker Jan 09 '14 at 18:10
@Dukeling So accessing the array in the other way arround when it is marked as reversed. In the example given, indeed the complexity is O(1). Thank you for the specification. – nmargaritis Jan 09 '14 at 18:22

score 0 · Answer 5 · answered Jan 09 '14 at 15:00

Recursion vs Iteration. Function calls (recursion) cost cycles. Thus, for this solution, I would go with an iterative approach. Other things to note are: even/odd sized arrays, empty arrays, arrays with only 1 item. An untested solution is:

void reverseArray(int arr[]){

  //check input
  if(arr.length <= 1){
    return;
  }

  int arrLength = arr.length;
  int swpIndex;

  for (int i = 0; i < arrLength / 2 - 1; i++){
    swpIndex = arrLength - i - 1;

    swp = arr[i];
    arr[i] = arr[swpIndex]; 
    arr[swpIndex] = swp;
  }
}

This stores a few values so that it really avoids repitition (i.e. extra cycles). It also checks for arrays that don't need reversing.

Fast Algorithm in Java to Reverse an Array

5 Answers5