|
|
Post by arnabbiswas on Apr 4, 2020 18:29:25 GMT -5
Given two sorted arrays, write a program that merges them in a sorted manner.
Input: arr1[] = { 1, 3, 4, 5}, arr2[] = {2, 4, 6, 8}
Output: arr3[] = {1, 2, 3, 4, 4, 5, 6, 8}
Input: arr1[] = { 5, 8, 9}, arr2[] = {4, 7, 8}
Output: arr3[] = {4, 5, 7, 8, 8, 9}
|
|
|
|
Post by deepak on Apr 5, 2020 13:39:26 GMT -5
Hope this not a trick question... ({} is set syntax not array  ) arr1 = [1,3,4,5] arr2 = [2,4,6,8] arr3 = sorted(arr1 + arr2) print(arr3) -------------------------- [1, 2, 3, 4, 4, 5, 6, 8] arr1 = [5,8,9] arr2 = [4,7,8] arr3 = sorted(arr1 + arr2) print(arr3) -------------------------- [4, 5, 7, 8, 8, 9] |
|
|
|
Post by arnabbiswas on Apr 6, 2020 13:42:37 GMT -5
Thanks Deepak. Thank you for pointing out and apologies for using dict notation instead of array.
Your answer works. But assume that the sorted function was not available to you, then how would you write this program? Most questions in Data Structures & Algorithms (DSA) assume non availability of such utility functions since their objective is to test the candidate's skill in writing such functions.
Also the sorted function has a complexity of O(nlogn). Can you write this program in O(n)
|
|
|
|
Post by deepak on Apr 6, 2020 13:53:59 GMT -5
Thanks Arnab. I just noticed your reply above. Let me try without built-in function "sorted".
Otherwise, if the solution was satisfactory, I was going to suggest extending your original quiz as below.
How to:
1) display only unique values (i.e. no duplicates)
2) display the frequency of the values (i.e. how many times the number appeared)
Taking the last example above, the results could look like:
1) 4,5,7,8,9
2)
4 - 1
5 - 1
7 - 1
8 - 2
9 - 1
|
|
|
|
Post by rajeshmenon on Apr 6, 2020 20:44:45 GMT -5
arr1=[10, 20, 30]
arr2=[6,16,19]
arr3=[None] * len(arr1 + arr2)
i=j=k=0
#print ("array3 - " + str(len(arr3)))
while i < len(arr1) and j < len(arr2):
# print("hello")
if arr1[i] < arr2[j]:
arr3[k]=arr1[i]
i=i+1
else:
# print("in else")
arr3[k]=arr2[j]
j=j+1
k=k+1
while i < len(arr1):
arr3[k] = arr1[i]
i=i+1
k=k+1
while j < len(arr2):
arr3[k] = arr2[j]
j=j+1
k=k+1
print(arr3)
|
|
|
|
Post by jeerav on Apr 12, 2020 21:15:14 GMT -5
I used Merge Sort and Merge Algorithms.
def merge_sort_func(in_arr):
if len(in_arr) > 1:
mid = len(in_arr) // 2
leftA = in_arr[:mid] #left array
rightA = in_arr[mid:] #right array
sortedA = in_arr #initialize
# Recursive call - Divide and Conquer
merge_sort_func(leftA)
merge_sort_func(rightA)
#Sort and Merge --------------------------------
#merge the left and right arrays into sortedA
li = 0 #left index
ri = 0 #right index
si = 0 #sorted array index
while (li < len(leftA)) and (ri < len(rightA)):
if (leftA[li]) < rightA[ri]:
sortedA[si] = leftA[li]
li += 1
else:
sortedA[si] = rightA[ri]
ri += 1
si += 1 #increment the sorted array index
#move any remaining left array items
while (li < len(leftA)):
sortedA[si] = leftA[li]
li += 1
si += 1
#move any remaining right array items
while (ri < len(rightA)):
sortedA[si] = rightA[ri]
ri += 1
si += 1
#-------------------
# main program
arr1 = [9, 5, 150, 4, 1, 350, 3]
arr2 = [250, 2, 8, 7, 6]
arr3 = arr1 + arr2
print('Before Sort: ', arr3)
merge_sort_func(arr3)
print('After Sort:', arr3)
|
|
|
|
Post by arnabbiswas on Apr 13, 2020 10:04:53 GMT -5
Exactly jeerav, merge sort uses this merge algorithm to merge multiple single element lists together into a single sorted list. We could discuss this in more detail in a subsequent class |
|
|
|
Post by arnabbiswas on Apr 13, 2020 10:12:18 GMT -5
Here's a follow up question on this merge algorithm - Given two sorted arrays, write a program that merges them in a sorted manner, without using an additional output array.Input: arr1 = [1, 3, 4, 5, 9, 11], arr2 = [2, 4, 6, 8] Output: arr1 = [1, 2, 3, 4, 4, 5], arr2 = [6, 8, 9, 11] Thus return 2 arrays of the same size as the input array but having elements that are sorted across both arrays Note: You cannot call the merge function and then split up the output to return the two arrays |
|
)
