4
\$\begingroup\$

I wrote a recursive sorting algorithm and was wondering what would be the run time complexity of this. The bulk of the work is done in the push_up function, which I think is linear in time. There are a linear amount of recursive calls though. If \$n\$ is the length of the list, would the runtime then be \$O(n^2)\$?

def sort(lst):
    """Recursive sorting algorithm. Sorts the remainder of the list 
    and then pushes the first element up to its appropriate position"""

   if lst == []:
       return []
   if len(lst) == 1:
       return [lst[0]]
   elt = lst[0]
   sorted_lst = sort(lst[1:])
   return push_up(elt, sorted_lst)

def insert(val, lst, i):
    """Inserts [val] into [lst] at index [i] """

    return lst[:i] + [val] + lst[i:]

def push_up(val, lst):
    """Pushes [val] up the list until it reaches its sorted position.
    Precondition: lst is sorted"""
    start = 0
    while start < len(lst) and lst[start] < val:
        start += 1

    return insert(val, lst, start)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ If I am not wrong that is insertion sort, which runs at $O(n^2)$ in worst case scenario. \$\endgroup\$ – QuIcKmAtHs Jan 1 '18 at 22:52
  • 1
    \$\begingroup\$ @XCoderX you need to backslash the dollar signs here to get mathjax. e.g. \$O(n^2)\$ is written \\$O(n^2)\\$ \$\endgroup\$ – Snowbody Jan 2 '18 at 4:07
4
\$\begingroup\$

Yes.

You can see that your sort function operates by recursing directly on itself, using a shorter-by-one version of its list parameter. This is stopped when the list is of length 0 or 1. (That code should be cleaned up.) So your sort recurses n-1 times, given n >= 2.

Each time it recurses, sort calls push_up once. The push_up function linearly scans the list, which is of length 1, then 2, then ... n-1.

So in the worst case (input array is reverse-sorted) you have scans of total length \$ \sum 1 ... (n-1) \$, which makes your code \$ O(n^2) \$.

\$\endgroup\$
4
\$\begingroup\$

I have a few suggestions for improving your code.

  • Good job using docstrings. Perhaps you should mention what the parameters actually represent, e.g. lst represents the list to be sorted.

  • if lst == []:
        return []
    if len(lst) == 1:
        return [lst[0]]
    

    This could be replaced by:

    if len(lst) <= 1:
        return lst[:]
    

    The [:] is slice notation for a copy of the entire list.

  • def insert(val, lst, i):
        """Inserts [val] into [lst] at index [i] """
    
        return lst[:i] + [val] + lst[i:]
    

    Since lst is already guaranteed to be a copy here, no need to make four new lists. Just insert the item into the existing lst and return it, e.g.

    lst.insert(i, val)
    return lst
    
  • def push_up(val, lst):
        """Pushes [val] up the list until it reaches its sorted position.
        Precondition: lst is sorted"""
        start = 0
        while start < len(lst) and lst[start] < val:
            start += 1
    

    It is not Pythonic to increment your own index to iterate over a list. Instead you should use the builtin enumerate:

    for (pos, item) in enumerate(lst):
        if item >= val:
            return insert(val, lst, pos)
    # if not found
    lst.append(item)
    return lst
    
\$\endgroup\$
1
  • \$\begingroup\$ The parentheses around pos and item are superfluous (though arguably better for readability). \$\endgroup\$ – Daniel Jan 2 '18 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.