How to sort negative numbers in the quick sort algorithm?

Question

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

Why do you think it's not working just for negative numbers? Your recursive calls modify new lists, not the original list. — jamesdlin
– jamesdlin, Commented Apr 8, 2019 at 2:11
numList[:left] creates a copy of numList with the specified range of elements. Same with numList[left+1:]. Consequently, calling quicksort on them has no effect on the original numList that was supplied. Thus you end up with the result of partitioning around only a single pivot (in your test case, 3). This has nothing to do with negative numbers, which a few more test cases could have easily shown. — jamesdlin
– jamesdlin, Commented Apr 8, 2019 at 2:32
And in general, I'd suggest an Occam's Razor mentality: it's more likely that your implementation simply doesn't work than it is that it works for everything but negative numbers. Don't jump to conclusions (and then suggest such unproven conclusions in your question). — jamesdlin
– jamesdlin, Commented Apr 8, 2019 at 2:38

recnac · Accepted Answer · 2019-04-08 02:42:25Z

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. : )

Collectives™ on Stack Overflow

How to sort negative numbers in the quick sort algorithm?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related