CODEWITHSUNDEEP
pythonsortingquicksort
Forstrei
Forstrei

Reputation: 3

Python Why is this quicksort not sorting properly?

I have been trying to implement the quicksort function using python for the last three weeks but I always get to this point and it sorts mostly, but there are a few items out of place.

I don't think I understand the quicksort properly, so if you can see why from my code please explain.

I have chosen the pivot to be the first object in the list, "low", and then comparing it to the rest of the list. If the object at list index "low" is greater than list index "i" (in my for loop), then I switch "i" with "E" (initially indexed to the item "low + 1"), if it does switch, "E" increments. Even if it doesn't switch, "i" increments (because of the for loop).

Once my loop is finished, I decrement "E" (to index it to the highest number in the list lower than my pivot) then switch it with "low" (index of pivot)

I then quicksort the left and right halves of the list using "E" to determine where the list splits. - this seems to be the point where the code fails to sort.

I believe this is how the quicksort works, but I haven't been able to make it work. If you know what I'm missing or if it's just one of my lines, please let me know. Any help with this problem would be greatly appreciated.

(PS. The "main" function is just passing a list of 20 length with variables of 0-19 value into my quicksort and the Python build-in sort)

import random


def quick(A, low, high):
    if high <= low:
        return
    elif high > low:
        E = low+1
        for i in range(E, high):
            if A[low] > A[i]:
                A[i], A[E] = A[E], A[i]
                E +=1
        E -= 1
        A[low], A[E] = A[E], A[low]
        quick(A, low, E-1)
        quick(A, E+1, high)


def main():
    listA = []
    listB = []
    for i in range(20):
        int = random.randrange(0, 19)
        listA.append(int)
    for i in range(len(listA)):
        listB.append(listA[i])
    print("List A (before sort)" + str(listA))
    print("List B (before sort)" + str(listB))
    quick(listA, 0, len(listA)-1)
    print("\nList A (after sort)" + str(listA))
    print("List B (before sort)" + str(listB))
    listB.sort()
    print("\nList A (after sort)" + str(listA))
    print("List B (after sort)" + str(listB))


main()

Upvotes: 0

Views: 143

Answers (1)

StephenTG
StephenTG

Reputation: 2647

Your problem is that you're ignoring one number with each split. range(min, max) gives a list that includes min but not max, ending rather on max-1

quick(listA, 0, len(listA)-1)

should be

quick(listA, 0, len(listA)),

and

quick(A, low, E-1)

should be

quick(A, low, E).

Upvotes: 5

Related Questions