CODEWITHSUNDEEP
pythonpython-3.xsortingquicksort
python_noob
python_noob

Reputation: 285

Problems in Quick Sort Code

I am having a problem with my Quick Sort code. I am new to coding and python(python 3.6), any help would be really appreciated. I have seen several implementations of Quick Sort online but I want to figure out what is really wrong with my code. I am pasting my code below: 

def Partition(A):
    q = A[0]
    i = 1
    for j in range(1, len(A)):
        if A[j] < q:
            A[j], A[i] = A[i], A[j]
            i = i + 1
    A[0], A[i - 1] = A[i - 1], A[0]
    return i - 1

def QuickSort(A):
    if len(A) <= 1:
        return A
    else:
        q = Partition(A)
        QuickSort(A[ : q])
        QuickSort(A[q + 1 : ])
        return A

A = [7, 5, 4, 1, 3, 6, 2, 8]
Sorted = []
Sorted = QuickSort(A)
print(Sorted)

For the input above I am getting the output [2, 5, 4, 1, 3, 6, 7, 8] instead of getting a sorted list in ascending order.

Upvotes: 2

Views: 112

Answers (1)

Stefan Pochmann
Stefan Pochmann

Reputation: 28596

These try to sort copied parts of A:

    QuickSort(A[ : q])
    QuickSort(A[q + 1 : ])

They return something, but you ignore what they return, so it's lost. You should write their results back into A:

    A[ : q] = QuickSort(A[ : q])
    A[q + 1 : ] = QuickSort(A[q + 1 : ])

After this change, your result is the expected [1, 2, 3, 4, 5, 6, 7, 8].

Upvotes: 4

Related Questions