Implementing Quick Sort in Python

Question

I am trying to implement quick sort. Looks simple, Implement a pivot function so that smaller elements and larger elements are gathered in two separate lists. Do this recursively, until lists are small enough to be sorted in constant time.

def pivot(a, pivot_index):
    # I guess you can keep two indexes one greater and one lesser and swap.
    i, j = 0, len(a)-2
    p = a[pivot_index]
    a[pivot_index] = a[len(a)-1]
    a[len(a)-1] = p

    while(i<j):
        if(a[i]<p):
            i = i + 1
        if(a[i]>p):
            temp = a[i]
            a[i] = a[j]
            a[j] = temp
            j = j - 1
        #print(a)
    return a[0:i], a[i:]

def quicksort(a):
    if len(a) <= 1:
        return a
    p = len(a)//2
    l1, l2 = pivot(a, p)
    return quicksort(l1) + quicksort(l2)

if __name__ == "__main__":
    a = [1,-9,288,91,3,4,58,67,8]
    print(quicksort(a))

I get the error:

Traceback (most recent call last):
  File "11.py", line 79, in <module>
    print(quicksort(a))
  File "11.py", line 73, in quicksort
    return quicksort(l1) + quicksort(l2)
  File "11.py", line 73, in quicksort
    return quicksort(l1) + quicksort(l2)
  File "11.py", line 73, in quicksort
    return quicksort(l1) + quicksort(l2)
  [Previous line repeated 993 more times]

Traceback (most recent call last):
  File "11.py", line 76, in <module>
    print(quicksort(a))
  File "11.py", line 70, in quicksort
    return quicksort(l1) + quicksort(l2)
  File "11.py", line 70, in quicksort
    return quicksort(l1) + quicksort(l2)
  File "11.py", line 70, in quicksort
    return quicksort(l1) + quicksort(l2)
  [Previous line repeated 993 more times]
  File "11.py", line 69, in quicksort
    l1, l2 = pivot(a, p)
  File "11.py", line 54, in pivot
    while(i<j):
RecursionError: maximum recursion depth exceeded in comparison

Probably what is happening is that the base case is never called in quicksort. But not sure how to fix it.

@cᴏʟᴅsᴘᴇᴇᴅ not working, but why it should be done in the first place?...pivot needs to run through the list... — mourinho
– mourinho, Commented Dec 29, 2017 at 4:42
At the start of each function, print the arguments so you know how the functions got called. You'll most certainly see repetition and can then easily find out how it happens. — Stefan Pochmann
– Stefan Pochmann, Commented Dec 29, 2017 at 4:43
I suggest spending a little time learning how to use the logging package rather than reaching for print for such debugging. But also structured walkthrough (whiteboard "testing") is still a valuable skill for this sort of algorithmic analysis. BE the CPU and walkthrough what the code is doing. — Jim Dennis
– Jim Dennis, Commented Dec 29, 2017 at 4:56
@JimDennis Hmm, what advantage does the logging package have here? Just seems like overkill to me. — Stefan Pochmann
– Stefan Pochmann, Commented Dec 29, 2017 at 5:04

Praveen · Accepted Answer · 2017-12-29 11:59:47Z

7

The below functionality explains how exactly the quicksort has been implemented by sending the input data as an array to the quicksort function. Here we implemented quicksort using recursion as below:

First check whether the array contains more than 1 element or not. If there is less than or equal to one element in the array then return array.(if len(arr) <= 1 then return arr)

Now take a pivot element from the middle of the array(Retrieve element from half the size of array) and then calculate the pivot element in the first iteration (pivot = arr[len(arr)//2])

If elements in array are less than pivot element then create a left array using list comprehension in python(left = [x for x in arr if x < pivot])

If elements in the array is equal to pivot element then create a middle array (middle = [x for x in arr if x == pivot])

If elements in the array are more than pivot element then create a right array (right = [x for x in arr if x > pivot])

Send the left array, right array to the quicksort function and repeat them recursively until all the elements in the array are sorted.

 def quicksort(arr):
          if len(arr) <= 1:
             return arr
          pivot = arr[len(arr)//2]
          left = [x for x in arr if x < pivot]
          middle = [x for x in arr if x == pivot]
          right = [x for x in arr if x > pivot]
          return quicksort(left) + middle + quicksort(right)

edited Dec 29, 2017 at 11:59

answered Dec 29, 2017 at 6:26

Praveen

9026 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Lino Over a year ago

Even when your post, answers OP's question. Please provide not only a snippet that works. But explain what's happening, why it does what it should to etc.

Praveen Over a year ago

@Lino: Yes , I have explained how it has been implemented using python

Collectives™ on Stack Overflow

Implementing Quick Sort in Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related