CODEWITHSUNDEEP
pythonrecursion
zeyuxie
zeyuxie

Reputation: 75

how to fix the sort function

def merge (l1,l2):
    if l1 and l2:
        if l1 == [] and l2 == []:
            return []
        if l1[0] > l2[0]:
            l1, l2 = l2, l1 
        return [l1[0]] + merge(l1[1:], l2)
    return l1 + l2


def sort(l):
    x = len(l) / 2
    x = int(x)
    y = merge(l[0:x], l[x+1:])
    return y

I need to write a recursive function named sort; it is passed any unordered list (all int or all str) and it returns a new list that contains every value from its argument list, but in sorted/non-descending order. But I cannot call any of Python’s functions/methods that perform sorting.

also, For any list that has at least 2 values, I have to break the list in half and recursively call sort to sort each smaller list, I have to use the merge function, written above, to merge these two sorted lists returned from these recursive calls

merge is a function to combine and sort two list

merge([1,3,5,8,12],[2,3,6,7,10,15]) returns [1,2,3,3,5,6,7,8,10,12,15].

For example, calling sort([4,5,3,1,6,7,2]) would call sort recursively on the lists [4,5,3] and [1,6,7,2]), returning the lists [3,4,5] and [1,2,6,7] respectively, which when merged would return the list [1,2,3,4,5,6,7].

My function got the following error

39 *Error: sort([1,2,3,4,5,6,7]) -> [1, 2, 3, 5, 6, 7] but should -> [1, 2, 3, 4, 5, 6, 7]
40 *Error: sort([7,6,5,4,3,2,1]) -> [3, 2, 1, 7, 6, 5] but should -> [1, 2, 3, 4, 5, 6, 7]
41 *Error: sort([4,5,3,1,2,7,6]) -> [2, 4, 5, 3, 7, 6] but should -> [1, 2, 3, 4, 5, 6, 7]
42 *Error: sort([1,7,2,6,3,5,4]) -> [1, 3, 5, 4, 7, 2] but should -> [1, 2, 3, 4, 5, 6, 7]

What is wrong with me sort method? can someone help me to fix it? thanks in advance.

Upvotes: 2

Views: 342

Answers (3)

Stefan Pochmann
Stefan Pochmann

Reputation: 28626

Three problems:

  • Your y = merge(l[0:x], l[x+1:]) loses l[x], make it y = merge(l[:x], l[x:]).
  • It doesn't sort the halves, so make it y = merge(sort(l[:x]), sort(l[x:])).
  • You have no base case, stopping the recursion when there's nothing to do.

Corrected and simplified a bit:

def sort(l):
    if len(l) <= 1:
        return l
    x = len(l) // 2
    return merge(sort(l[:x]), sort(l[x:]))

The // is integer division so you don't need the extra int(...). And no point in creating that y variable.

Btw, the if l1 == [] and l2 == []: test inside if l1 and l2: is pointless (if l1 and l2 were [], you wouldn't get inside the if l1 and l2: block in the first place), so you can remove it.

One more thing: While your merge function isn't wrong, it's slow. Every l1[1:] takes time proportional to the length of l1. You'd better uses indexes, like for example in Huy Vo's answer.

Upvotes: 2

Huy Vo
Huy Vo

Reputation: 2500

What you need is a merge sort, I believe there are multiple merge sort pseudocodes on the internet.

Anyway, here is a version of mine in Python 3:

def mergesort(lst):
    if len(lst) < 2:
        return lst
    else:
        middle = len(lst) // 2
        # recursion, baby
        left_half = mergesort(lst[:middle])
        right_half = mergesort(lst[middle:])
        return merge(left_half, right_half)

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        elif left[i] > right[j]:
            result.append(right[j])
            j += 1
    result += left[i:] + right[j:]
    return result

Upvotes: 0

tactic
tactic

Reputation: 57

Ok basically everything you're doing is redundant.

list1 = [1,3,5,8,12]
list2 = [2,3,6,7,10,15]

list3 = list1 + list2 # Merges lists

list3_sorted = sorted(list3) # Sorts them

Also a little bonus, if you have a list of lists or tuples and you want to sort by an index of each of those

from operator import itemgetter

list = [(2,6), (3,4)]
list_sorted = sorted( list, key=itemgetter(1) ) # Will sort by index 1 of each item.

Edit: I now realise that you can't use any built in functions, give me a little to mess around and see if I can figure something out

Upvotes: 0

Related Questions