Hi C++ programmer. At the bottom is a working version of your code, and let me show you some problems you had.
def quick_sort(array):
test_array = []
test_array.append(array)
if len(test_array) == 1:
return array
This is the first problem. test_array
is an empty array, and you append an array to it, so test_array
will always have one element, and just return the original.
Python comes with an interactive interpreter, so play with that.
>>>> x = []
>>>> y = [1,2,3,4]
>>>> x.append(y)
>>>> x
[[1, 2, 3, 4]] # note nested array here
>>>> len(x)
1
All in all too many parenthesis. Python doesn't need so many parenthesis.
Plus, unsorted_list is a tuple, not an array to start with. Tuples are defined by using commas, and the parenthesis does nothing.
>>>> x = 1,2,3
>>>> type(x)
<type 'tuple'>
>>>> x = [1,2,3]
>>>> type(x)
<type 'list'>
This error was repeated with the sorted_array
in your quicksort routine, so sorted_array becomes a tuple.
No need for the extraneous int()
calls, the duck quacks int()
so it is an int.
Working version below:
def quick_sort(array):
#test_array = []
#test_array.append(array)
if len(array) < 2:
return array
array_left = []
array_right = []
pivot = array[0]
for i in range(1,len(array)):
if array[i] >= pivot:
array_right.append(array[i])
else:
array_left.append(array[i])
sorted_array = quick_sort(array_left) + [pivot] + quick_sort(array_right)
return sorted_array
def main():
unsorted_list = [2,3,69,1,7,2,5,5,4,4,5,2,2,5,5,5,2,1,9,8,8,7,8,5,2,1,4,5,215,2,4,5,1]
print 'unsortedlist:\n', unsorted_list, '\n\n'
sorted_list = quick_sort(unsorted_list)
print 'sortedlist:\n', sorted_list, '\n\n'
if __name__ == '__main__':
main()