I am not getting output from the quick sort

Question

I am not getting output from the quick sort code below:

def quick_sort(sequence):
    length = len(sequence)
    if length<=1:
        return sequence
    else:
        pivot = sequence.pop()
        item_greater = []
        item_lower = []
        for item in sequence:
            if item> pivot:
                item_greater.append(item)

            else:
                item_lower.append(item)
                print( quick_sort(item_lower) + [pivot]  + quick_sort(item_greater))

Testing the quicksort algorithm:

print(quick_sort([91,45,78,124,174,32,75,69,43,15,2,45,19,66]))

You are not actually returning the results. You are simply printing them out. Edit: it also missing a lot of code. See: https://www.geeksforgeeks.org/python-program-for-quicksort/ for reference — Larry the Llama, Dec 10 '21 at 05:29

score 1 · Answer 1 · answered Dec 10 '21 at 05:31

1

Return your values instead of printing them out:

def quick_sort(sequence):
    length = len(sequence)
    if length<=1:
        return sequence
    else: pivot = sequence.pop()
    item_greter = []
    item_lower = []
    for item in sequence:
        if item > pivot: item_greter.append(item)

        else:
            item_lower.append(item)
            return quick_sort(item_lower) + [pivot]  + quick_sort(item_greter)
            
print(quick_sort([91,45,78,124,174,32,75,69,43,15,2,45,19,66]))

answered Dec 10 '21 at 05:31

krmogi

2,588
1
10
26

1

Even this still doesn't work - he's missing a whole bunch of code to begin with. – Larry the Llama Dec 10 '21 at 05:32
Also a pity that this has a worse indentation pattern than the Asker used. – trincot Dec 10 '21 at 07:51

trincot · Answer 2 · 2021-12-10T08:23:57.050

These are the main issues:

Your function does not return the results, so you'll get None back from the recursive call and then the + [pivot] operation will raise an error.
Related to the previous point: when the recursive result comes back, it should not be printed. Printing should only happen when the final result is ready, i.e. this is a job for the original caller (in the main code).
The recursive call should not be made in the loop where you populate the two partitions. It should be made after that loop

Not a problem, but the spelling of "greter" is "greater"

Also, you can skip the first else, as the if block will end in a return.

Correction:

def quick_sort(sequence):
    length = len(sequence)
    if length <= 1:
        return sequence
    pivot = sequence.pop()
    item_greater = []
    item_lower = []
    for item in sequence:
        if item > pivot: 
            item_greater.append(item)
        else:
            item_lower.append(item)
    return quick_sort(item_lower) + [pivot]  + quick_sort(item_greater)


print(quick_sort([91,45,78,124,174,32,75,69,43,15,2,45,19,66]))

Final remarks

It is not nice that this function destroys the input list. If the caller has a reference to that list and inspects it after the call, it will lack one element. This is due to the first pop that is executed on it:
```
lst = [91,45,78,124,174,32,75,69,43,15,2,45,19,66]
print(quick_sort(lst))
print(lst)  # misses the last element and is not sorted
```
Quick sort is intended to be an in-place sorting algorithm, so you should not need to create new lists (item_greater and item_greater). Instead these partitions should be formed by swapping values in the input list. There should be no [] (new empty list) or + (list concatenation) in such an implementation.

Correct versions of in-place quick sort algorithms are readily available. There are many variants possible, depending on the pivot selection. Also on this site there are several Q&A on the topic. See for instance:

I am not getting output from the quick sort

2 Answers2

Final remarks