CODEWITHSUNDEEP
pythonquicksort
user839148
user839148

Reputation:

QuickSort is returning correct values, but not sorting in place

I'm struggling to understand why my QuickSort returns the sorted values correctly, but the resulting array is not sorted correctly. 

def qSort(array):
    n = len(array)
    if (n == 1 or n ==0):
            return array
    p_index = partition(array)
    p_value = array[p_index]
    return(qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n]))

def partition(array):
    pivot = array[0]
    i = 1
    for j in xrange(1,len(array)):
        print j
        if array[j] < pivot:
            tmp = array[j]
            array[j] = array[i]
            array[i]=tmp
            i += 1
    tmp = array[i-1]
    array[i-1] = pivot
    array[0] = tmp
    return i-1

Here is some sample output:

>>> q = [5,4,3,2,1]
>>> qSort(q)
[1, 2, 3, 4, 5]
>>> q
[1, 4, 3, 2, 5]

Thank you in advance!

Upvotes: 2

Views: 181

Answers (4)

PaulH
PaulH

Reputation: 11

If you want to return the array and also sort in place you should before returning make the array equal to the result and not make a new one. You can do that by changing your return statement to:

    array[:] = qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n])
    return array

Note that 

    array = qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n])

does not work either, because the lhs variable will be treated as a local variable.

Upvotes: 0

Sukrit Kalra
Sukrit Kalra

Reputation: 34493

This is because you are making up a new list in your return statement.

return(qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n]))

If the qSort function reaches a base case, it returns a list, which is concatenated with [p_value] and returned as a list. You do not make changes to the passed in list anywhere.

When you call your qSort function recursively, you are giving it a slice of the list and the function returns the list in the base case which you then append to the pivot and the other recursive call, hence generating a new list.

See what is happening by changing your qSort function to

def qSort(array):
    n = len(array)
    if (n == 1 or n ==0):
            return array
    p_index, array = partition(array)
    p_value = array[p_index]
    returnVal = qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n])
    print "Returning:", returnVal, "Original Array:", array
    return returnVal

Output -

>>> q = [5,4,3,2,1]
>>> qSort(q)
Returning: [2, 3] Original Array: [2, 3]
Returning: [2, 3, 4] Original Array: [2, 3, 4]
Returning: [1, 2, 3, 4] Original Array: [1, 4, 3, 2]
Returning: [1, 2, 3, 4, 5] Original Array: [1, 4, 3, 2, 5]
[1, 2, 3, 4, 5]

To reflect the changes in your original list, you have the option of doing q = qSort(q).

P.S - Setting up a random index instead of the first value would be better for your quicksort function. See the bit here on Choice of Pivots.

Upvotes: 1

Lee Daniel Crocker
Lee Daniel Crocker

Reputation: 13171

In Python, slicing and combining lists create new lists. If you want your recursive calls to operate on a single list in place, pass the list and the bounds into the call, and don't return anything from the function. Something like:

def qsort(array, low, high):
    if high-low < 2:
        return

    # Choose pivot, do partition within bounds

    if partition > low:
        qsort(array, low, partition)
    if partition < high:
        qsort(array, partition+1, high)

Then just call qsort(a, 0, len(a)) to sort the array.

Upvotes: 1

Toni V
Toni V

Reputation: 41

apply the function back to q

q = qSort(q)

Upvotes: 0

Related Questions