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