how to define sort_tuple that returns a tuple in ascending order

Question

I need to define a function 'sort_tuple' that takes in a tuple and returns a tuple sorted in ascending order. (I am not supposed to use the built-in function sorted or .sort in the code)

Note: the code should make use of the insert_tuple function:

def insert_tup(x, tup):
    b = search(x, tup)
    left = tup[:b]
    right = tup[ b:]
    new_tup = left + (x,) + right
    return new_tup

def search(x, seq):
    for i in seq:
        if x<i:
            return seq.index(i)
        elif x == i:
            return seq.index(i)
        elif x>seq[-1]:
            return (seq.index(seq[-1]))+1

Test result:

>>> sort_tuple((5, 0, -1, 4, -2))
(-2, -1, 0, 4, 5)

Here's my answer:

def sort_tuple(tup):
    for i in range(len(tup)):
       if tup[i-1] > tup[i]:
            removed_tup = tup[0:i-1] + tup[i: len(tup)]
            new_tup = insert_tup(tup[i-1], removed_tup)
    return new_tup

But this code fails because when i type in this expression:

sort_tuple((5, 0, -1, 4, -2))

the output should be in ascending order:(-2, -1, 0, 4, 5) but my output is (4, 5, 0, -1, -2).

Answer 1

You should probably do a kind of insertion sort:

def sort_tuple(t):
    result = () # start with an empty result
    for val in t:
        result = insert_tup(val, result) # insert each value into its place
    return result

This is not terribly efficient, but it is very easy to do with the functions you've been given to work with.

While the code above is very straight forward, in this case it is only working by a fluke, as the search function behaves badly (returning None) when passed an empty tuple. Fortunately tup[:None] is a legal slice. In the specific situation it comes up in, it's even correct!

A better implementation of search would return an integer always. Here's a quick stab at it:

def search(x, seq):
    for i, v in enumerate(seq):
        if x < v:
            return i
    return len(seq)

Or better still, use the bisect module to do the searching in O(log n) time rather than O(n).