CODEWITHSUNDEEP
javascriptarrays
Ivan
Ivan

Reputation: 10372

Javascript's Array Reverse

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.

Upvotes: 7

Views: 1910

Answers (2)

Narendra Yadala
Narendra Yadala

Reputation: 9664

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;
}

Upvotes: 3

James Allardice
James Allardice

Reputation: 165951

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 .

Upvotes: 6

Related Questions