7

How exactly does Javascript's array.reverse() work? Does it go through and swap every element of the array? If so, does it take O(n) to swap an array of size n?

I guess the reason I am asking is because I was wondering if array.reverse() was the same as:

for(var i = 0; i < a.length / 2; i++) {
  var holder = a[i];
  a[i] = a[a.length - 1 - i];
  a[a.length - 1 - i] = holder;
}

NOTE: Sorry if the Javascript code I posted is incorrect, it's pretty late right now.

EDIT: Fixed a.length to a.length / 2.

Improve this question
1
  • 2
    It's incorrect because by traversing the array in full, you'll swap all the elements twice and return to the original array. Use a.length / 2 (integer division of a.length and 2) Commented Oct 27, 2011 at 7:19

2 Answers 2

Reset to default
6

For the full details of how it works, read the relevant section of the spec. Here's the algorithm:

  1. Let O be the result of calling ToObject passing the this value as the argument.

    1. Let lenVal be the result of calling the [[Get]] internal method of O with argument "length".
    2. Let len be ToUint32(lenVal).
    3. Let middle be floor(len/2).
    4. Letlower be 0.

    5. Repeat, while lower ≠ middle

      1. Let upper be len−lower −1.
      2. Let upperP be ToString(upper).
      3. Let lowerP be ToString(lower).
      4. Let lowerValue be the result of calling the [[Get]] internal method of O with argument lowerP.
      5. Let upperValue be the result of calling the [[Get]] internal method of O with argument upperP .
      6. Let lowerExists be the result of calling the [[HasProperty]] internal method of O with argument lowerP.
      7. Let upperExists be the result of calling the [[HasProperty]] internal method of O with argument upperP.

      8. If lowerExists is true and upperExists is true, then

      9. Call the [[Put]] internal method of O with arguments lowerP, upperValue, and true .

      10. Call the [[Put]] internal method of O with arguments upperP, lowerValue, and true .
      11. Else if lowerExists is false and upperExists is true, then
      12. Call the [[Put]] internal method of O with arguments lowerP, upperValue, and true .
      13. Call the [[Delete]] internal method of O, with arguments upperP and true.
      14. Else if lowerExists is true and upperExists is false, then
      15. Call the [[Delete]] internal method of O, with arguments lowerP and true .
      16. Call the [[Put]] internal method of O with arguments upperP, lowerValue, and true .
      17. Else, both lowerExists and upperExists are false
      18. No action is required.
      19. Increase lower by 1.
    6. Return O .
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

The actual algorithm is almost similar to what you specified. Just change your for loop to iterate only upto a.length/2 and it would be similar to what Array.reverse would do. I am skipping the inner details here for the sake of simplicity. So it would be 

for(var i = 0; i < a.length/2; i++) {
  var holder = a[i];
  a[i] = a[a.length - 1 - i];
  a[a.length - 1 - i] = holder;
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.