I am not getting output from the quick sort-CodePudding

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]))

CodePudding user response：

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]))

CodePudding user response：

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: