In-place quicksort algorithm in Python 2

Question

I have tried to implement an in-place quicksort Algorithm in Python 2. Please suggest how I can

1. Make the code more efficient
2. Increase readability
3. Improve writing style
4. Make it more Pythonic

def swap(x,y):
 return y,x
def sort(ar, start, end, l):
 if start<end-1:
 # pivot element is taken as the last element
 p = ar[end-1]
 ind=start-1
 # when a smaller no. than pivot is found, swap it with first bigger-tahn-pivot element. 
 # keep index as the recently swapped smaller integer, if no smaller number found, than index is start-1 because pivot is out as first element
 for i in xrange(start,end-1):
 if ar[i]<p:
 ind=i
 for j in xrange(0,i):
 if ar[j]>p:
 ind=j
 ar[i],ar[j] = swap(ar[i],ar[j])
 break
 #Swap pivot with the first bigger-than-pivot number 
 ar[ind+1], ar[end-1] = swap(ar[ind+1], p)
 ar = sort(ar, start, ind+1, l)
 ar = sort(ar, ind+2, end, l)
 return ar
 else:
 return ar

• alisianoi: unnecessarily indenting your code is, imo, a poor decision. Instead of making a huge if start < end - 1: pass else: pass, I would suggest making a if start >= end - 1: return ar at the beginning and unindenting the rest of the body.
• alisianoi: I would also suggest properly spacing your code: start < end - 1 instead of start<end-1 and so on.

Answer 1

Your swap function is pointless. It would be far more clear just to switch the order directly in the right hand side of every assignation.

Also, in the second for loop. I'm not sure you're supposed to iterate from 0. At best it should be from start. Remember, the idea of quicksort is that you only modify the part of the array that corresponds to the function, [start, end) in this case. However, with that loop, you're now making O(n^2) iterations, which can be improved like this:

p = ar[end-1]
idx_le = start
idx_gt = end-2
while idx_le <= idx_gt:
 if ar[idx_le] <= p:
 idx_le += 1
 else:
 ar[idx_gt], ar[idx_le] = ar[idx_le], ar[idx_gt]
 idx_gt -= 1
ar[idx_le], ar[end-1] = ar[end-1], ar[idx_le]
return ar

The main idea is to keep track where the elements less than p should be placed, same with the elements greater than p. The new recursion should be [start, idx_le) [idx_le+1, end).

• dc95: For above code, For input: [1, 3, 9, 8, 2, 7, 5]; after completion of the first while loop, the updated array is printed: [1, 3, 5, 8, 2, 7, 9]. Which is not right. The final answer is also not sorted. I agree my code consumes unnecessary time, but your code does not seem to work. Am I missing something? Could you please check your code? Maybe post the whole function?
• Santiago: My apologies. You are right, when I wrote the code I didn't thoughtfully tested it. I've updated with a version that should be working and uses pretty much the same approach.