Python sorting list with negative number [duplicate]

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.

"So the list is sorted however the negative integers are sorted in reverse order." - no; the negative integers aren't sorted in any order, because there aren't any negative integers, because there aren't any integers. — Karl Knechtel
– Karl Knechtel, Commented Mar 6, 2023 at 7:41

ShadowRanger · Accepted Answer · 2017-02-24 03:51:04Z

3

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.

answered Feb 24, 2017 at 3:51

ShadowRanger

158k12 gold badges221 silver badges314 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ishiro Kusabi Over a year ago

Thank you! I mapped the int to the list and everything works. So it was not the error in code, but error in the type I was sorting and its behaviors. Thank you ShadowRanger. I learnt alot!

bballdave025 Over a year ago

Thanks for including both python2 and python3 implementations. +1 for that. I think this is easier and more clean than doing the type conversion for each integer to be compared.

Joseph Sible-Reinstate Monica · Accepted Answer · 2017-02-24 03:46:20Z

1

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.

answered Feb 24, 2017 at 3:46

Joseph Sible-Reinstate Monica

49k7 gold badges55 silver badges118 bronze badges

Comments

Hugo · Accepted Answer · 2017-02-24 03:48:15Z

1

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.

answered Feb 24, 2017 at 3:48

Hugo

6125 silver badges10 bronze badges

Collectives™ on Stack Overflow

Python sorting list with negative number [duplicate]

3 Answers 3

2 Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Linked

Related