9
\$\begingroup\$

Reversing an array in Python without using a built-in function:

def reverse(alist):
    end = len(alist)-1
    limit = int(end/2) + 1
    for i in range(limit):
        alist[i],alist[end] = alist[end],alist[i]
        end = end - 1
    return alist

print reverse([1,2,3,4,5,6])
\$\endgroup\$
  • 3
    \$\begingroup\$ One small question: Do you consider slices as being built-ins ? Or are you strictly speaking about the reversed() built-in ? If not, you could do def reverse(alist): return alist[::-1] \$\endgroup\$ – Grajdeanu Alex. Feb 17 '17 at 17:54
  • 1
    \$\begingroup\$ @Dex'ter Yes, i am considering slice as built-ins here, also alist[::-1]. \$\endgroup\$ – Akan Feb 17 '17 at 17:56
12
\$\begingroup\$

The first solution that comes to mind is to take advantage of the powerful list comprehension and abuse the xrange function:

def reverse(some_list):
    return [some_list[n] for n in xrange(len(some_list) - 1, -1, -1)]

The above is nothing more than the usual reversed for loop that you may find in other languages (like C / C++) as:

for (int i = array.length - 1; i >= 0; i--)  
{  
    // Do something ...  
}  

Details about the range function can be found here but basically, all you have to know about it is its prototype:

range(start, stop[, step])

which is very descriptive.

I'd go with this instead of your solution because it looks cleaner and I don't see any reasons of why it'd be slower or harder to understand.

\$\endgroup\$
  • \$\begingroup\$ Why not xrange? \$\endgroup\$ – hjpotter92 Feb 20 '17 at 2:04
  • \$\begingroup\$ @MrGrj xrange returns an iterable rather than building a list. It would function perfectly in your example, and would mean you had about half the memory usage for larger lists. \$\endgroup\$ – Challenger5 May 1 '17 at 6:10
  • \$\begingroup\$ I forgot it had Python 2.x tag ^_^. Hehe \$\endgroup\$ – Grajdeanu Alex. May 1 '17 at 6:11
9
\$\begingroup\$

Calculating the limit is a tad annoying, because you have to carefully verify to not make an off-by-one error. It would be easier to loop until the indexes cross each other:

def reverse(alist):
    left = 0
    right = len(alist) - 1
    while left < right:
        alist[left], alist[right] = alist[right], alist[left]
        left += 1
        right -= 1

I made some other changes as well:

  • Adjusted formatting to follow PEP8
  • I renamed the index variables to more natural left, right
  • I dropped the return statement, because it might mislead users to assume that the returned list is a new list, which is not the case, because the function modifies the content of the input list.
\$\endgroup\$
3
\$\begingroup\$

Few stylistic points about your current solution:

  • use print() as a function for Python 3 compatibility
  • on the other hand, because you are running it on Python 2.x, you may avoid creating an extra list with range() and use xrange() function (differences)
  • according to PEP8, you need to have spaces around the operators
  • you can use end -= 1 shortcut instead of end = end - 1

The code with all the proposed changes applied:

def reverse(alist):
    end = len(alist) - 1
    limit = int(end / 2) + 1
    for i in xrange(limit):
        alist[i], alist[end] = alist[end], alist[i]
        end -= 1
    return alist

print(reverse([1, 2, 3, 4, 5, 6]))

Note that you don't have to return the alist from the function, since your reverse operates "in-place" - it modifies the input list. In other words, if you would remove return alist and run:

l = [1,2,3,4,5,6]
reverse(l)
print(l)

You would see [6, 5, 4, 3, 2, 1] printed.


One more way to do the reverse "manually" can be to use the negative indexing (not sure if it fits your constraints):

def reverse(alist):
    return [alist[-i] for i in range(1, len(alist) + 1)]

Or, an expanded version without a list comprehension:

def reverse(alist):
    newlist = []
    for i in range(1, len(alist) + 1):
        newlist.append(alist[-i])
    return newlist

Note that this is not working in place, it would return a new list.

\$\endgroup\$
2
\$\begingroup\$

Variation of shortest version in @alecxe's answer: since you want answer[i] to be alist[len(alist) - 1 - i] = alist[-1 - i] = alist[~i]:

def reverse(alist):
    return [alist[~i] for i in xrange(len(alist))]
\$\endgroup\$
1
\$\begingroup\$

Presuming modifying in place is desired, negative indexing can be quite helpful:

def reverse(a):
   for i in range(len(a)/2):
      a[i], a[-(i+1)] = a[-(i+1)], a[i]

and I can ignore the possible off-by-one an odd number causes because all that will change is whether the center number will swap with itself.

\$\endgroup\$
  • \$\begingroup\$ You can use ~i rather than -(i + 1). \$\endgroup\$ – Challenger5 May 1 '17 at 6:11
1
\$\begingroup\$

Another short version:

def reverse(l):
    return [l.pop() for _ in range(len(l))]

pop removes the last item from a list and returns it.
The original list will be emptied by this function:

>>> l = [0, 1, 2]
>>> reverse(l)
[2, 1, 0]
>>> l
[]
\$\endgroup\$
  • \$\begingroup\$ This is a strong constraint to have a function that both modifies the input list in place and produce a new list. What if I want to zip(l, reverse(l))? Now I can't. \$\endgroup\$ – 409_Conflict Feb 9 '18 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.