CODEWITHSUNDEEP
pythonalgorithmsorting
durga
durga

Reputation: 434

merge sort algorithm - counting inversions

Understandably there are multiple threads created for merge sort algorithms and counting inversions. While this is a homework problem for a course on coursera, I am having difficulty in understanding where my implementation is going wrong in counting number of inversions. I seem to be getting very unrealistically low values for few test examples as compared to others taking the course. Below is my code:

count = 0
def sort_list(unsortedlist):

    m = len(unsortedlist)

    A_list = unsortedlist[:m/2]
    B_list = unsortedlist[m/2:]


    if len(A_list) > 1: # if the list is longer thn 2 items, break it up
        A_list = sort_list(A_list)


    if len(B_list) > 1: # breaking and sorting second part
        B_list = sort_list(B_list)

    return merge_sort(A_list,B_list) # merge the smaller lists to return either a-list/b_list or full_list        

def merge_sort(a_list,b_list):

    initiallist = a_list+b_list
    final_list = []
    i = 0
    j = 0
    global count

    while len(final_list) < (len(initiallist)):

        if len(a_list) != 0 and len(b_list) != 0:
            if  a_list[i] < b_list[j]:
                final_list.append(a_list.pop(i))

            elif a_list[i] > b_list[j]:
                final_list.append(b_list.pop(j))
                count += 1

            elif a_list[i] == b_list[j]:
                final_list.append(a_list[i])
                final_list.append(b_list[j])


        elif len(b_list) == 0 :
            final_list+=a_list


        elif len(a_list) == 0 :
            final_list+=b_list

    print count

    return final_list

Upvotes: 1

Views: 3692

Answers (1)

AbcAeffchen
AbcAeffchen

Reputation: 15007

The Problem is, that you are counting only 1 inversion, if a_list[i] > b_list[j] is true.

But since both lists are sorted at this point, it means you get an inversion for every element that is in a_list. So you have to use count += len(a_list) instead of count += 1.

Example:

a_list = [5,6,7,8] and b_list = [1,2,3,4]

  1. 5 > 1
    • final_list = [1]
    • you get four inversions: (5,1), (6,1), (7,1), (8,1)
  2. 5 > 2
    • final_list = [1,2]
    • you get four inversions: (5,2), (6,2), (7,2), (8,2)
  3. 5 > 3
    • final_list = [1,2,3]
    • you get four inversions: (5,3), (6,3), (7,3), (8,3)
  4. 5 > 4
    • final_list = [1,2,3,4]
    • you get four inversions: (5,4), (6,4), (7,4), (8,4)
  5. b_list is empty
    • append a_list to final_list and get final_list = [1,2,3,4,5,6,7,8]
    • no more inversions

Upvotes: 5

Related Questions