Quicksort in Python

Question

L = [7, 12, 1, -2, 0, 15, 4, 11, 9]


def quicksort(L, low, high):
    if low < high:
        pivot_location = Partition(L, low, high)
        quicksort(L,low, pivot_location)
        quicksort(L,pivot_location + 1, high)
    return L

def Partition(L, low, high):
    pivot = L[low]
    leftwall = low
    for i in range(low + 1, high, 1):
        if L[i] < pivot:
            temp = L[i]
            L[i] = L[leftwall]
            L[leftwall] = temp
            leftwall += 1
    temp = pivot
    pivot = L[leftwall]
    L[leftwall] = temp
    return leftwall

print(quicksort(L, 0, len(L) - 1))

When I run the code it produces the following result: [-2, 0, 1, 4, 7, 11, 12, 15, 9]. One element is at the wrong position. If anyone could tell me where the problem is ?

high should be len(L)... And you should split on low,pivot and pivot,high (so not pivot+1). — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Mar 11, 2017 at 9:53
Only change I made and the code worked is len(L) instead of (len(L) - 1). The splitting is correct. — user6420403
– user6420403, Commented Mar 11, 2017 at 10:06

Menglong Li · Accepted Answer · 2017-03-11 11:24:38Z

1

Here I just show u another simple way to implement Q_Sort in Python:

def q_sort(lst):
    return [] if not lst else q_sort([e for e in lst[1:] if e <= lst[0]]) + [lst[0]] + q_sort([e for e in lst[1:] if e > lst[0]])


L = [7, 12, 1, -2, 0, 15, 4, 11, 9]

print q_sort(L)

and we get:

[-2, 0, 1, 4, 7, 9, 11, 12, 15]

answered Mar 11, 2017 at 11:24

Menglong Li

2,25517 silver badges21 bronze badges

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

3 Comments

Javier Over a year ago

Note that OP's qsort is modifying the array inplace, this one creates new lists (if lists are very large this might be an issue)

Menglong Li Over a year ago

Yeah, I agree, this method just shows the core concept of quick sort including partition. This is not used in project, but can be used to show the magic of Python

user6420403 Over a year ago

Yes, I liked that implementation. It really shows the magic of Python despite the fact that it should be used only for small lists!

user6420403 · Accepted Answer · 2017-03-11 10:13:29Z

1

I just changed this line of code and it worked fine:

quicksort(L, 0, len(L))

instead of

quicksort(L, 0, len(L) - 1)

answered Mar 11, 2017 at 10:13

user6420403

Collectives™ on Stack Overflow

Quicksort in Python

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related