1

The questions are: 1) Is that correct code to count comparisons? 2) How can I return counter with sorted list like ([1,2,3,4], number_of_comparisons) Code:

counter = 0
def merge_sort(lst):
"""Sorts the input list using the merge sort algorithm.

>>> lst = [4, 5, 1, 6, 3]
>>> merge_sort(lst)
[1, 3, 4, 5, 6]
"""
if len(lst) <= 1:
    return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right), counter

def merge(left, right):
"""Takes two sorted lists and returns a single sorted list by comparing the elements one at a time.

>>> left = [1, 5, 6]
>>> right = [2, 3, 4]
>>> merge(left, right)
[1, 2, 3, 4, 5, 6]
"""
global counter
if not left:
    return right
if not right:
    return left
counter += 1
if left[0] < right[0]:
    return [left[0]] + merge(left[1:], right)
return [right[0]] + merge(left, right[1:])


lst = [4, 5, 1, 6, 3]
print(merge_sort(lst))

Output: 

([1,3,4,5,6], counter)
Alex Mahino
  • 11
  • 1
  • 4

2 Answers2

0

The answer is yes, this code may count the number of comparisons, but you have to clearly understand what do you want to count

Here are some modifications, you may remove them if you don't need them

counter = 0


def merge_sort(lst):
    global counter
    if len(lst) <= 1:
        counter += 1 # increment counter when we dividing array on two
        return lst
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left, right)


def merge(left, right):
    global counter
    if not left:
        counter += 1 # increment counter when not left (not left - is also comparison)
        return right
    if not right:
        counter += 1 # the same as above for right
        return left
    if left[0] < right[0]:
        counter += 1 # and the final one increment
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])


lst = [4, 5, 1, 6, 3]
# also you don't need to return counter since you are using global value
print(merge_sort(lst), counter)

Also you may try to look here!

Community
  • 1
  • 1
Laser
  • 6,652
  • 8
  • 54
  • 85
  • Thanks a lot! It works. But I still need to modify this code so my final output should be `([1,3,4,5,6], counter)`. Doesn't have an idea how to do it. – Alex Mahino Oct 15 '16 at 08:20
  • When I'm trying to do it inside the function, recursion just reset my counter to 0 every time. – Alex Mahino Oct 15 '16 at 08:23
  • Could you please add example in your question – Laser Oct 15 '16 at 09:14
  • I posted the answer. Also, if you have a possibility to help me to count the number of comparisons in quick_sort method. Code is next: – Alex Mahino Oct 15 '16 at 09:51
  • Just check the code here, http://stackoverflow.com/questions/18262306/quick-sort-with-python and modify it as you want : – Laser Oct 15 '16 at 09:53
0

I've found a solution in that way:

def merge_sort(input_array):
counter = 0

if len(input_array) <= 1:
    return input_array, counter

left_part = merge_sort(input_array[:len(input_array) // 2])
right_part = merge_sort(input_array[len(left_part[0]):])

counter += left_part[1] + right_part[1]

left_ndx = 0
right_ndx = 0
final_ndx = 0

while left_ndx < len(left_part[0]) and right_ndx < len(right_part[0]):
    counter += 1
    if left_part[0][left_ndx] < right_part[0][right_ndx]:
        input_array[final_ndx] = left_part[0][left_ndx]
        left_ndx += 1
    else:
        input_array[final_ndx] = right_part[0][right_ndx]
        right_ndx += 1
    final_ndx += 1

while left_ndx < len(left_part[0]):
    input_array[final_ndx] = left_part[0][left_ndx]
    left_ndx += 1
    final_ndx += 1
    counter += 1

while right_ndx < len(right_part[0]):
    input_array[final_ndx] = right_part[0][right_ndx]
    right_ndx += 1
    final_ndx += 1
    counter += 1

return input_array, counter

So the output would be:

([1,3,4,5,6], counter)
Alex Mahino
  • 11
  • 1
  • 4