current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite

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
share|improve this question

1 Answer 1

up vote 2 down vote accepted

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).

share|improve this answer
    
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? –  Darshil Chauhan Dec 29 '14 at 18:19
    
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. –  Santiago Dec 29 '14 at 18:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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