Main Menu

Merge Two Sorted Arrays

Started by kevin, January 03, 2023, 09:10:22 PM

Previous topic - Next topic

kevin

   Merged Sorted Arrays

 This function takes two two sorted Integer (Numeric) and merged them into a new array.  




PlayBASIC Code: [Select]
   Size=100

Dim Test1(Size)
Dim Test2(Size)

; fill both arrays with some random integers between 0 and 1000
for lp =0 to Size
Test1(lp)=rnd(1000)
Test2(lp)=rnd(1000)
next

; Place a couple of value at the end of our arrays to check we're
; getting all the values in the merged output
test1(Size) = 5000
test2(Size) = 9999


; Sort the Arrays
SortArray Test1(),0,Size
SortArray Test2(),0,Size


Dim Result(0)


Result()=MergeSortedArrays(Test1(), Test2())

Sync
waitkey




Function MergeSortedArrays(a(), b())

; dim our arrat C() to hold both merged arrays
A_Size =getarrayelements(a())
B_Size =getarrayelements(b())



; output array total size
C_Size = A_Size+B_Size+1
Dim c(C_Size)

; Initialize variables to track the current position in each array
i = 0
j = 0
for LP=0 to C_Size
; Check if the value in array A is
; smaller than the value in array B

if a(i) < b(j)
; Add the value from array A to the merged array
c(lp) = a(i)
i++ ; Move to the next element in array A

; Check if we're out of values in array A
if i>A_Size
; If so, we copy the rest of B() to C()
For CopyLP = j to B_Size
LP++
c(LP)=b(CopyLP)
next

endif

Else

; Otherwise, the value in array B is smaller
; Add the value from array B to the merged array
c(lp) = b(j)
j++ ; Move to the next element in array B

; Check if we're out of values in array B
if j>B_Size

; if so, we can copy the rest of A() to C()
For CopyLP = i to A_Size
LP++
c(lp)=a(CopyLP)
next
endif

Endif

next lp
; Return the merged array
EndFunction c()







   Learn To Code How it Works:

   The function called MergeSortedArrays takes two sorted arrays, a and b, as input and returns a new array containing the merged and sorted values from both input arrays.

   The function starts by declaring a new array, c, to hold the merged values of the two input arrays. It then initializes three variables, i, j, and lp, which will be used to track the current position in each of the input arrays and to loop through the elements of the output array.

   The function then enters a FOR loop which will iterate lp from 0 to the size of the output array. Inside the loop, the function compares the current element of array a to the current element of array b. If the element from array a is smaller, it is added to the merged array and the i variable is incremented to move to the next element in array a. If the element from array b is smaller, it is added to the merged array and the j variable is incremented to move to the next element in array b.

  If the end of either array a or b is reached, the rest of the values in the other array are added to the output array in a separate FOR loop. Finally, the function returns the merged array c.