CODEWITHSUNDEEP
pythonrecursionquicksort
Alex
Alex

Reputation: 49

Python quicksort recursive depth

I am trying to find how far the recursive function descends i.e the deepest level of recursion, in the following quick sort code, i have been told to edit the qsort function and would appreciate any help

def partition(lst, lo, hi):
    part = lo
    while lo < hi:
           while lst[lo] <= lst[part] and lo < hi:
                lo += 1
           while lst[hi] > lst[part]: # Don't have to check for hi >= 0 cos part is there as a sentinel.
                hi -= 1
           if lo < hi:
               # Swap the two entries
               lst[hi], lst[lo] = lst[lo], lst[hi]
       # Swap part into position
    if lst[part] > lst[hi]: # (this may happen of the array is small (size 2))
            lst[part], lst[hi] = lst[hi], lst[part]
    print(part)
    return hi
def rec_qsort(lst, lo, hi):
    if lo < hi:
       pivot = partition(lst, lo, hi)
       rec_qsort(lst, lo, pivot - 1)
       rec_qsort(lst, pivot + 1, hi)
def qsort(lst):
    rec_qsort(lst, 0, len(lst) - 1)
    return lst

Upvotes: 0

Views: 390

Answers (1)

Kenny Ostrom
Kenny Ostrom

Reputation: 5871

Pass depth as an optional parameter, default 0, to your implementation function rec_qsort. Add one when you recurse deeper.

def function(data, depth=0):
    if len(data) > 1:
        mid = len(data)/2
        function(data[:mid], depth+1)
        function(data[mid:], depth+1)
    print "depth", depth, "length", len(data), data

data = range(10)
function(data)

Obviously print at the beginning if you want to see the order of calls, print at the end if you want them in order by when they return. Add a watch instead of printing if you just want to see depth while debugging.

from user pjs: The maximum depth of quicksort, measured directly, can be anything between log(n) and n. The expected depth for randomized data or a randomly selected pivot is proportional to log(n)

Upvotes: 1

Related Questions