1

I am using quick sort to put my list in order. The list is full of numbers formatted as such:

1999.03,0.9
2000.08,0.1
1988.1,0.8

the number before the decimal point is a year and the number after the decimal point is the month. The number after the comma is a price. My quick sort puts them in order, however it drops the price after I do it and I do not know why. I am new to python so I may not be doing this the best way, but I'd still like someone to show me why this doesnt work

def quick_sort(arr):
    if arr == []:
        return []
    else:
        element = arr[len(arr)/2]
        pivot = float(element[0:7])
        lesser = quick_sort([x for x in arr[1:] if float(x[0:7]) < pivot])
        greater = quick_sort([x for x in arr[1:] if float(x[0:7]) >= pivot])
        return lesser + [pivot] + greater

The output looks like:

1988.1
1999.03
2000.08

I assume its the syntax in the recursive call of quicksort, however I do not know enough about python to spot it.

Improve this question
2
  • "I am using quick sort to put my list in order." Why not leave it to Timsort? Commented Jun 3, 2014 at 19:40
  • 3
    I am new to python and wanted to try and make something work in it that I had been able to do in C++. This exercise was to help me learn python, not achieve the project in the most effective manner Commented Jun 3, 2014 at 19:41

1 Answer 1

Reset to default
2

You cut the pivot to compare it with the other cuts. It's here you drop the part. You have to keep the entire element :

element = arr[len(arr) / 2]
pivot = float(element[:7])

So you can compare with your variable pivot and the result list is build with the element part.

The build of the result is done with :

return lesser + [element] + greater
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Exactly so. If it weren't for the fact that OP is a novice Python-er, I'd recommend using a collections.namedtuple to keep track of it. arr = [ your, existing, array ], "array_element = namedtuple("array_element", ["data","sort_info"]), new_arr = [array_element(el, float(el[:7])) for el in arr], then run your quick_sort returning [el.data for el in new_arr if el.sort_info < pivot.sort_info] + [pivot.data] + [el.data for el in new_arr if el.sort_info >= pivot.sort_info]
2 named variable are more readable than namedtuple in this case. There is 4 variable in the entire function. Namedtuple are used to represent a semi-complex state between different call. Here there is only one short function
@TurplF: Confession: I just recently learned about namedtuple and have now been using it for everything I can. Coordinate = namedtuple(data=['x','y']) is a common one :). I've become one of those "When all you have is a hammer everything you see is a nail" coders. HELP ME!
@AdamSmith: this kind of use is good because you pass your position between different context/function/processus/something and it's correctly packed with named reference to the data. In the case of only one context, it's useless.
@AdamSmith I put the element before my pivot, but it did not change the output
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.