What Is the Most Efficient Way to Reverse an Array in JavaScript

What is the most efficient way to reverse an array in Javascript?

Based on this setup:

var array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var length = array.length;

Array.reverse(); is the first or second slowest!

The benchmarks are here:

https://jsperf.com/js-array-reverse-vs-while-loop/9

Across browsers, swap loops are faster. There are two common types of swap algorithms (see Wikipedia), each with two variations.

The two types of swap algorithms are temporary swap and XOR swap.

The two variations handle index calculations differently. The first variation compares the current left index and the right index and then decrements the right index of the array. The second variation compares the current left index and the length divided by half and then recalculates the right index for each iteration.

You may or may not see huge differences between the two variations. For example, in Chrome 18, the first variations of the temporary swap and XOR swap are over 60% slower than the second variations, but in Opera 12, both variations of the temporary swap and XOR swap have similar performance.

Temporary swap:

First variation:

function temporarySwap(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0, right = length - 1; left < right; left += 1, right -= 1)
    {
        var temporary = array[left];
        array[left] = array[right];
        array[right] = temporary;
    }
    return array;
}

Second variation:

function temporarySwapHalf(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0; left < length / 2; left += 1)
    {
        right = length - 1 - left;
        var temporary = array[left];
        array[left] = array[right];
        array[right] = temporary;
    }
    return array;
}

---

XOR swap:

First variation:

function xorSwap(array)
{
    var i = null;
    var r = null;
    var length = array.length;
    for (i = 0, r = length - 1; i < r; i += 1, r -= 1)
    {
        var left = array[i];
        var right = array[r];
        left ^= right;
        right ^= left;
        left ^= right;
        array[i] = left;
        array[r] = right;
    }
    return array;
}

Second variation:

function xorSwapHalf(array)
{
    var i = null;
    var r = null;
    var length = array.length;
    for (i = 0; i < length / 2; i += 1)
    {
        r = length - 1 - i;
        var left = array[i];
        var right = array[r];
        left ^= right;
        right ^= left;
        left ^= right;
        array[i] = left;
        array[r] = right;
    }
    return array;
}

---

There is another swap method called destructuring assignment:
http://wiki.ecmascript.org/doku.php?id=harmony:destructuring

Destructuring assignment:

First variation:

function destructuringSwap(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0, right = length - 1; left < right; left += 1, right -= 1)
    {
        [array[left], array[right]] = [array[right], array[left]];
    }
    return array;
}

Second variation:

function destructuringSwapHalf(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0; left < length / 2; left += 1)
    {
        right = length - 1 - left;
        [array[left], array[right]] = [array[right], array[left]];
    }
    return array;
}

Right now, an algorithm using destructuring assignment is the slowest of them all. It is even slower than Array.reverse();. However, the algorithms using destructuring assignments and Array.reverse(); methods are the shortest examples, and they look the cleanest. I hope their performance gets better in the future.

---

Another mention is that modern browsers are improving their performance of array push and splice operations.

In Firefox 10, this for loop algorithm using array push and splice rivals the temporary swap and XOR swap loop algorithms.

for (length -= 2; length > -1; length -= 1)
{
    array.push(array[length]);
    array.splice(length, 1);
}

However, you should probably stick with the swap loop algorithms until many of the other browsers match or exceed their array push and splice performance.

How can I reverse an array in JavaScript without using libraries?

Javascript has a reverse() method that you can call in an array

var a = [3,5,7,8];
a.reverse(); // 8 7 5 3

Not sure if that's what you mean by 'libraries you can't use', I'm guessing something to do with practice. If that's the case, you can implement your own version of .reverse()

function reverseArr(input) {
    var ret = new Array;
    for(var i = input.length-1; i >= 0; i--) {
        ret.push(input[i]);
    }
    return ret;
}

var a = [3,5,7,8]
var b = reverseArr(a);

Do note that the built-in .reverse() method operates on the original array, thus you don't need to reassign a.

Is JS array.reverse() O(1) or O(n)

Time complexity O(n): https://learnersbucket.com/examples/algorithms/how-to-reverse-an-array-in-javascript/

Should I not worry about the computational efficiency for just a few thousand items?

For a few thousand items, you will probably not notice the difference. In general, most projects are small enough where they do not benefit from such efficiencies like these. However on the flip side, if you implement two or three of these inefficiencies in the same project, you will start to see issues with delays in time.

In terms of remaining as time efficient as possible, your second approach is probably the most efficient way to handle this, as you are taking two O(n) operations (switching all the elements in the array, and adding a ',' to the end of each) and putting them together into a single operation.

Node.JS - Reversing Massive Arrays Efficiently?

Could you just read the array in reverse instead of reversing it? You could also create a wrapper class around Array e.g., ReversibleArray which uses the same backing array instance but could be read forwards or backwards depending on some property like readInReverse: true|false on instances of that class.

javascript reverse an array without using reverse()

array.pop() removes the popped element from the array, reducing its size by one. Once you're at i === 4, your break condition no longer evaluates to true and the loop ends.

---

One possible solution:

function reverse(array) {  var output = [];  while (array.length) {    output.push(array.pop());  }
  return output;}
console.log(reverse([1, 2, 3, 4, 5, 6, 7]));

Reverse array in Javascript without mutating original array

You can use slice() to make a copy then reverse() it

var newarray = array.slice().reverse();

var array = ['a', 'b', 'c', 'd', 'e'];var newarray = array.slice().reverse();
console.log('a', array);console.log('na', newarray);

Reversing an array of objects in Javascript

console.log() takes into account whether a mutable object has changed before it has been printed on the screen. And as your process of OUTPUT -> CHANGE -> OUTPUT is almost plesiochronous, both outputs are the same. You have to use a copy of x in order to get the prompt you need.

Try it this way:

// copy x
y = Object.assign({}, x);
console.log(y);

x.reverse();
console.log(x);  

---

Related Topics