problem sorting out quicksort

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()
/r/learnpython Thread