Reverse array in place

Question

Why won't this function reverseArrayInPlace work?

I want to do simply what the function says—reverse the order of elements, so that the results end up in the same array arr. I am choosing to do this by using two arrays in the function. So far it just returns the elements back in order...

    var arr = ["a","b","c","d","e","f"]
    var arr2 = []

    var reverseArrayInPlace = function(array){

      var arrLength = array.length
      for (i = 0; i < arrLength; i++) {
        arr2.push(array.pop())
        array.push(arr2.shift())
      }
    }

    reverseArrayInPlace(arr)

Habakkuk

also, javascript already has a built in in-place array reverse – Copperplate

doing an array exercise which specifies that I cannot use those methods. I'm trying to work with the push, pop, shift, unshift functions – Habakkuk

en.wikipedia.org/wiki/In-place_algorithm – Katey

@Copperplate the reference is passed by value, so it's actually working. – Ferritin

Answer 1

Here's a simpler way of reversing an array, using an in-place algorithm

function reverse (array) {
  var i = 0,
      n = array.length,
      middle = Math.floor(n / 2),
      temp = null;

  for (; i < middle; i += 1) {
     temp = array[i];
     array[i] = array[n - 1 - i];
     array[n - 1 - i] = temp;
  }
}

You "split" the array in half. Well, not really, you just iterate over the first half. Then, you find the index which is symmetric to the current index relative to the middle, using the formula n - 1 - i, where i is the current index. Then you swap the elements using a temp variable. The formula is correct, because it will swap:

0 <-> n - 1
1 <-> n - 2

and so on. If the number of elements is odd, the middle position will not be affected.

Katey

Answer 2

pop() will remove the last element of the array, and push() will append an item to the end of the array. So you're repeatedly popping and pushing just the last element of the array.

Rather than using push, you can use splice, which lets you insert an item at a specific position in an array:

var reverseArrayInPlace = function (array) {
    var arrLength = array.length;
    for (i = 0; i < arrLength; i++) {
        array.splice(i, 0, array.pop());
    }
}

(Note that you don't need the intermediate array to do this. Using an intermediate array isn't actually an in-place reverse. Just pop and insert at the current index.)

Also, interesting comment—you can skip the last iteration since the first element will always end up in the last position after length - 1 iterations. So you can iterate up to arrLength - 1 times safely.

I'd also like to add that JavaScript has a built in reverse() method on arrays. So ["a", "b", "c"].reverse() will yield ["c", "b", "a"].

A truly in-place algorithm will perform a swap up to the middle of the array with the corresponding element on the other side:

var reverseArrayInPlace = function (array) {
    var arrLength = array.length;
    for (var i = 0; i < arrLength/2; i++) {
        var temp = array[i];
        array[i] = array[arrLength - 1 - i];
        array[arrLength - 1 - i] = temp;
    }
}

Nonferrous

I can see what you mean if I used the same push pop, push pop methods, but I am using push pop, push, shift. Besides, I have tried switching shift to pop and I still end up with arr = ["a","b","c","d","e","f",] – Habakkuk

Any combination of push, pop, shift, and unshift will just move around the elements in order. For [a, b, c], imagine popping and shifting several times; you get [c, a, b], then [b, c, a], and finally [a, b, c]. So you're doing nothing to the array. – Nonferrous

Hey @AustinSefton, did my explanation make sense? You see why your code wasn't working, right? – Nonferrous

Answer 3

If you are doing Eloquent JavaScript, the exercise clearly states to not use a new array for temporary value storage. The clues in the back of the book present the structure of the solution, which are like Stefan Baiu's answer.

My answer posted here uses less lines than Stefan's since I think it's redundant to store values like array.length in variables inside a function. It also makes it easier to read for us beginners.

function reverseArrayInPlace(array) {

    for (var z = 0; z < Math.floor(array.length / 2); z++) {
        var temp = array[z];
        array[z] = array[array.length-1-z];
        array[array.length-1-z] = temp;
    }
    return array;
}

Sadoc

There isn't anyone by the name "Stefan Baiu" here. What answer does it refer to? – Kennithkennon

Answer 4

You are calling the function with arr as parameter, so both arr and array refer to the same array inside the function. That means that the code does the same as:

var arr = ["a","b","c","d","e","f"]
var arr2 = []

var arrLength = arr.length;
for (i = 0; i < arrLength; i++) {
  arr2.push(arr.pop())
  arr.push(arr2.shift())
}

The first statements get the last item from arr and places it last in arr2. Now you have:

arr = ["a","b","c","d","e"]
arr2 = ["f"]

The second statement gets the first (and only) item from arr2 and puts it last in arr:

arr = ["a","b","c","d","e","f"]
arr2 = []

Now you are back where you started, and the same thing happens for all iterations in the loop. The end result is that nothing has changed.

---

To use pop and push to place the items reversed in the other array, you can simply move the items until the array is empty:

while (arr.length > 0) {
  arr2.push(arr.pop());
}

If you want to move them back (instead of just using the new array), you use shift to get items from the beginning of arr2 and push to put them at the end of arr:

while (arr2.length > 0) {
  arr.push(arr2.shift());
}

---

Doing a reversal in place is not normally done using stack/queue operations, you just swap the items from the beginning with the items from the end. This is a lot faster, and you don't need another array as a buffer:

for (var i = 0, j = arr.length - 1; i < j; i++, j--) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

This swaps the pairs like this:

["a","b","c","d","e"]
  |   |       |   |
  |   +-------+   |
  +---------------+

Parasite

To avoid having to do your last while loop you could also start off by doing an arr2=arr.splice(0,n) and then doing your fist while with reversed roles: while(arr2.length)arr.push(arr2.pop()). – Unearth

@cars10: The point was to show how to do it using stack/queue operations, as the OP attempted. There are of course several simpler ways to do it. – Parasite

Answer 5

I think you want a simple way to reverse an array.

var yourArray = ["first", "second", "third", "...", "etc"]
var reverseArray = yourArray.slice().reverse()

console.log(reverseArray)

You will get

["etc", "...", "third", "second", "first"]

Showman

No, that was a set constraint (though it shouldn't be in comments): "JavaScript already has a built in in-place array reverse ... [I am] doing an array exercise which specifies that I cannot use those methods. I'm trying to work with the push, pop, shift, unshift functions" – Kennithkennon

Answer 6

With the constraints I had for this assignment, this is the way I figured out how to solve the problem:

var arr = ["a","b","c","d","e","f"]
var arr2 = []

var reverseArrayInPlace = function(array){

      var arrLength = array.length
      for (i = 0; i < arrLength; i++) {
        arr2.push(array.pop())
      }
      for (i = 0; i < arrLength; i++) {
        array[i] = arr2.shift()
      }
    }

      reverseArrayInPlace(arr)

Thank you for all your help!

***** edit ******

For all of you still interested, I rewrote it using some help from this thread and from my own mental devices... which are limited at this point. Here is it:

    arr = [1,2,3,4,5,6,7,8,9,10,11,12,13]
    arr2 = ["a","b","c","d","e","f"]
    arr3 = [1,2,3]
    arr4 = [1,2,3,4]
    arr5 = [1,2,3,4,5]


    var reverseArrayInPlace2 = function(array) {

      var arrLength = array.length
      var n = arrLength - 1
      var i = 0
      var middleTop = Math.ceil(arrLength/2)
      var middleBottom = Math.floor(arrLength/2)

      while (i < Math.floor(arrLength/2)) {

        array[-1] = array[i]
        array[i] = array[n]
        array[n] = array[-1]
        // console.log(array)
        i++
        n--

      }

      return array
    }

    console.log(reverseArrayInPlace2(arr))
    console.log(reverseArrayInPlace2(arr2))
    console.log(reverseArrayInPlace2(arr3))
    console.log(reverseArrayInPlace2(arr4))
    console.log(reverseArrayInPlace2(arr5))

P.S. what is wrong with changing global variables? What would the alternative be?

Habakkuk

I'm not sure it really counts as "in-place", but I'm glad you've solved your issue – Katey

It is generally not a good idea to have a function change a global variable (in your case arr2). Read what @Parasite wrote in his answer. He covered it very well! – Unearth

I was surprised by how much the three major approaches ( JS-built in, pop/push and swap in place) differed in speed, see here: jsperf.com/reverse-builtin-vs-optimised#run – Unearth

thank you @cars10 I understand what you mean. I will avoid that in the future. – Habakkuk

"what is wrong with changing global variables?" You might be applying the function in different places. If you actually relied on using the changed global variable in the first place then changing that in a subsequent call might lead to very confusing behaviour. This "side effect" is not at all transparent to the unsuspecting user who expects to have just the array changed in place. The alternative should be to work with a local variable (declare it inside the function) and - if you really want to return that valriable - attach it to the returned object or array as a property. – Unearth

Answer 7

Here is my solution without any temporary array. It is nothing groundbreaking, just a shorter version of some proposed solutions.

let array = [1, 2, 3, 4, 5];

 for(let i = 0; i<Math.floor((array.length)/2); i++){
     var pointer = array[i];
     array[i] = array[ (array.length-1) - i];
     array[(array.length-1) - i] = pointer;
 }

 console.log(array);
 //[ 5, 4, 3, 2, 1 ]

Adulterer

Answer 8

This is similar to the approved answer, but I use array destructuring instead of a temporary variable to swap the elements in the array.

const reverseArrayInPlace = array => {
  for (let i = 0; i < array.length / 2; i++) {
   [array[i], array[array.length - 1 - i]] = [array[array.length - 1 - i], array[i]]
 }
  return array
}

const myArray = [1,2,3,4,5,6,7,8,9];
console.log(reverseArrayInPlace(myArray))

Mclane

Answer 9

This solution uses a shorthand for the while

var arr = ["a","b","c","d","e","f"]

const reverseInPlace = (array) => {
  let end = array.length;
  
  while(end--)
    array.unshift(array.pop());
    
  return array;
}

reverseInPlace(arr)

Mutinous

All this is doing is cycling through the array and ultimately returning the same array.. – Heartsick

Why the weird formatting at the beginning and the end? What is the intent? – Kennithkennon

Answer 10

Best solution

export function reverseArrayInPlace(array) {
  let leftI = 0;
  let rightI = array.length - 1;

  while (leftI < rightI) {
    [array[leftI], array[rightI]] = [array[rightI], array[leftI]];

    leftI++;
    rightI--;
  }
}

Almonte

Answer 11

function reverseArrayInPlace (arr) {
  var tempArr = [];
  for (var i = 0; i < arr.length; i++) {
    // Temporarily store last element of original array
    var holdingPot = arr.pop();
    // Add last element into tempArr from the back
    tempArr.push(holdingPot);
    // Add back value popped off from the front
    //  to keep the same arr.length
    //  which ensures we loop thru original arr length
    arr.unshift(holdingPot);
  }
  // Assign arr with tempArr value which is the reversed
  //  array of the original array
  arr = tempArr;
  return arr;
}

Stralsund