Utilizing Mergesort for an array of unsorted words

user_15526530 0
Viewed 90

I'm trying to utilize mergesort + divide & conquer by taking a user's input of random words. I'm taking the users input and dividing the words given into two arrays:

import math

inputted_sentence = input("Enter your sentence here: \n")
separated_inputs = [word.lower() for word in inputted_sentence.split()]
inputs_length = int(len(separated_inputs))


#separate the arrays
array_one = (separated_inputs[0:math.floor(int(inputs_length/2))])
array_two = (separated_inputs[math.floor(int(inputs_length/2)):inputs_length])


#grab length of the array
length_array_one = len(array_one)
length_array_two = len(array_two)

after that, I'm sorting them (alphabetical order)

#first array being sorted and stored

for a in range(length_array_one-1):
    for b in range(length_array_one-a-1):
        if array_one[b] > array_one[b+1]:
            array_one[b], array_one[b+1] = array_one[b+1], array_one[b]

sorted_array_one = []

for words in array_one:
    sorted_array_one.append(words)


#second array being sorted and stored

for a in range(length_array_two-1):
    for b in range(length_array_two-a-1):
        if array_two[b] > array_two[b+1]:
            array_two[b], array_two[b+1] = array_two[b+1], array_two[b]

sorted_array_two = []

for words in array_two:
    sorted_array_two.append(words)

This image shows the two arrays: https://i.stack.imgur.com/9ZrHb.png

Now I need to compare blue to aaple, see it's less, compare blue to apple, see its less, blue to cat, see it is greater and it takes index[2] in the final array.

after that, rabbit compares with cat, its less, dog, it's less, takes the array spot after dog.

Edit: my version one (below) does this but this doesn't utilize the sorted arrays as it just sorts the words all over again.

unsorted_final = sorted_array_one + sorted_array_two
 
 
length_unsorted_final = len(unsorted_final)
 
sorted_array_final = []
 
#Final array sorted and stored
 
for a in range(length_unsorted_final-1):
    for b in range(length_unsorted_final-a-1):
        if unsorted_final[b] > unsorted_final[b+1]:
            unsorted_final[b], unsorted_final[b+1] = unsorted_final[b+1], unsorted_final[b]
 
 
for words in unsorted_final:
    sorted_array_final.append(words)
 
print(sorted_array_final)
mergesort arrays python
1 Answers

Merge sort uses a helper algorithm called "merge", which works by taking 2 sorted arrays, M and N, and combining them into a new array S that is also sorted. It does this by taking advantage of a simple invariant: given these 2 sorted input arrays, the smallest element in their union will always be either m = M[0] or n = N[0], and this remains true even after repeatedly removing the smaller of either m or n. If m <= n then we can do S.append(M.pop(0)), removing m from M UNION N and adding it to the end of S, and the invariant will still be true. We can keep doing this until both input lists are empty, leaving S = M UNION N and S is sorted.

you can implement that in Python like this:

def merge(left, right):
    result = []
    while left or right:
        if left and right:
            if left[0] <= right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        elif left:
            result.extend(left)
            break
        else:
            result.extend(right)
            break
    return result

Note that this is not quite MergeSort. This is actually just the merge step. To turn this into a fully working MergeSort, you need to implement the divide and conquer part. The most straightforward way of doing that is by taking the single input list and repeatedly splitting it in half, calling merge_sort on each half, then merging them:

def mergesort(A, depth=0):
    if (count := len(A)) > 1:
        left = mergesort(A[:count // 2], depth + 1)
        right = mergesort(A[count // 2:], depth + 1)
        print("{D}A: {A}\n{D}left: {L}\n{D}right: {R}".format(A=A, L=left, R=right, D="  " * depth))
        result = merge(left, right)
        print("{D}result: {S}".format(S=result, D="  " * depth))
        return result
    return A

(print statements and depth parameter added for demo purposes. This is not the most efficient way of implementing this, but I think it is the most illustrative.)

Hopefully you see how this works: since merge requires 2 sorted lists, we need to make sure to provide that. We do that by breaking the input down into smaller and smaller lists, until they only contain 1 element, which is trivially sorted. Then we proceed to build up longer and longer lists of sorted elements, until the whole input is done. I think the takeaway here is this: MergeSort is divide and conquer. Or, perhaps more accurately, MergeSort is the "divide" part, and the merge procedure is the "conquer".

user_66897250
Related