Python sorting list with negative number

Question

In attempt to learn python by practicing, I am trying to implement and test out quick sort algorithm using python.

The implementation itself was not difficult, however the result of the sort is somewhat puzzling:

When I sort a list

['35', '-1', '-2', '-7', '-8', '-3', '-4', '20', '-6', '53']

the result gives me

['-1', '-2', '-3', '-4', '-6', '-7', '-8', '20', '35', '53']

So the list is sorted however the negative integers are sorted in reverse order.

I suspect this may be the problem with the fact that I am sorting a list of ints read in from a file, and the type of the int is actually not int but something else (string, perhaps.) What could I possibly do to fix this problem?

here is the code for the quicksort implementation

#quicksort -> the conquer part of the algorithm
def quicksort(input_list, start_index, end_index):
    if start_index < end_index:
        #partition the list of integers.
        pivot = partition(input_list, start_index, end_index)
        #recursive call on both sides of the pivot, that is excluding the pivot itself
        quicksort(input_list, start_index, pivot-1)
        quicksort(input_list, pivot+1, end_index)
    return input_list

#divide part of the algorithm
def partition(input_list, start_index, end_index):
    #declare variables required for sorting
    pivot = input_list[start_index]
    left = start_index + 1
    right = end_index
    sorted = False

    while not sorted:
        #break condition so that left index is crossed with right index
        #or if the value of left crosses the pivot value
        while left <= right and input_list[left] <= pivot:
            #increment left index
            left = left + 1
        #break the loop when right and left indexes cross
        #or if the right value crosses the pivot value
        while right >= left and input_list[right] >= pivot:
            right = right-1
        if right < left:
            sorted = True
        else:
            #swap places for left value and the right value cause they are not in order
            temp = input_list[left]
            input_list[left] = input_list[right]
            input_list[right] = temp
    #swap the value at start index with what's now at the right half. Then return right for the new pivot
    temp = input_list[start_index]
    input_list[start_index] = input_list[right]
    input_list[right] = temp
    return right

Any help is appreciated. Thank you all for your time and help.

Solution 1

Your code is behaving correctly, since strings sort lexicographically (by first character, then second if first matches, then third if second matches, etc.). If you want to sort numerically, the easiest way is to fix up your list so it's actually int values:

# Possibly read from file as list of string
strlist = ['35', '-1', '-2', '-7', '-8', '-3', '-4', '20', '-6', '53']

intlist = map(int, strlist)  # list(map(int, strlist)) on Python 3

quicksort(intlist)

You could convert back to str afterwards if needed. Otherwise, your alternative is to implement support for a key function (that lets you sort values on a computed value) like list.sort/sorted, but that's probably more complex that you want to deal with right now.

Solution 2

You're sorting strings rather than numbers, so they're sorting in alphabetical order rather than numerical order. The int() function can turn strings into numbers.

Solution 3

Your numbers are all strings. If you're only expecting positive or negative whole numbers in your input, wrap them with int() when the comparison is made.