CODEWITHSUNDEEP
pythonpython-3.x
Samin Alam
Samin Alam

Reputation: 39

How to sort negative numbers in the quick sort algorithm?

I am trying to use the quick sort algorithm to sort a random of list of any numbers, but do not know how to sort negative numbers as well, which part of the code should I work on?

Didn't know what to do, commenting out the change of code will help out a lot.

Expected Results:

>>> quickSort([3,5,-3,-1,1,2,4])
[-3, -1, 1, 2, 3, 4, 5]

Actual Results:

>>> quickSort([3,5,-3,-1,1,2,4])
[1, 2, -3, -1, 3, 4, 5]

def quickSort(numList):

    n=len(numList)
    if n<=1:
        return numList
    x, left, right = numList[0], 0, n-1
    while left<right:
        if numList[left]<=x:    
            left+=1
        else:
            numList[left], numList[right]  =  numList[right], numList[left]
            right -=1
    numList[0], numList[left] = numList[left], numList[0]
    quickSort(numList[:left])
    quickSort(numList[left+1:])
    return numList

Upvotes: 2

Views: 1953

Answers (1)

recnac
recnac

Reputation: 3744

The unexpected result is not caused by negative number, but several bugs in your quick sort algorithm. I have fixed them just based on your version, although it is not the best version to implement. you can compare revised code and read the comment to understand.

A fatal bug I want to point out is, numList[:left] will slice and generate a new array, it will not effect origin array when you sort on it. So you should pass the array, and left, right index to quickSort function, not slice.

def quickSort(numList, left, right):
    # change check condition to left < right
    # n = len(numList)
    # if n <= 1:
    #     return numList
    if left < right:
        # copy left, right, it will used later
        low, high = left, right

        # it is better to abstract this block to a new function, like partition
        # pick a pivot number
        x = numList[left]
        while left < right:
            # you should use two-pointer to swap
            while left < right and numList[right] >= x:
                right -= 1
            numList[left] = numList[right]

            while left < right and numList[left] <= x:
                left += 1
            numList[right] = numList[left]
            # if numList[left] <= x:
            #     left += 1
            # else:
            #     numList[left], numList[right] = numList[right], numList[left]
            #     right -= 1

        # assign back the pivot number
        numList[left] = x
        # numList[0], numList[left] = numList[left], numList[0]

        # use origin arr and index, not slice 
        quickSort(numList, low, left-1)
        quickSort(numList, left+1, high)
        # quickSort(numList[:left])
        # quickSort(numList[left + 1:])
    return numList

test and output

arr = [3, 5, -3, -1, 1, 2, 4]
print(quickSort(arr, 0, len(arr)-1))
# [-3, -1, 1, 2, 3, 4, 5]

Hope that will help you, and comment if you have further questions. : )

Upvotes: 4

Related Questions