How to merge sorted arrays within arrays into a third sorted array

Question

The title may be confusing and forgive me as I am still a beginner. This is part of a HW assignment for school and although I am not looking for the answer outright I need a push in the right direction, or any help at all. So onto the question...

I need to create a simple program based on the code in class to merge multiple sorted arrays into one sorted array to output to the screen. The arrays are hardcoded in as "test cases" to uncomment and verify. The instuctors directions are as follows

Using the merge program developed in class (see attached) as a base, create a version that will merge 0 (zero) to n arrays of numbers. Hints: Sort the arrays before merging Use the shift method to remove the first item in an array (arrayName.shift()) To create an array of arrays ---> var x = [ ]; var y = [ ]; var z = [ x, y ];

EDIT: I have emailed the instructor with a solution based on the answer given by @cpugourou and his reply was that he will not accept that solution. The point of the homework is to manually merge these arrays.

Below is the original "Merge Program" that we developed in class

"use strict";   // reduces chance for error

/* 
    there are 2 arrays here and this program will merge them.
    Your job is to merge zero or more arrays. Test cases include:
    1. arrays with no elements: x = [], y = [], z = [], ...
    2. 2 arrays - one with elements and one without: x = [], y = [200, 39,1]
    3. 4 arrays: x = [5, 1, 0], y = [], z = [78, 3], w = [4, 34]
*/
var x = [ 12, 5, 1], y = [ 13, 2, 3], z = [];   // x and y are input and, after processing, z has the merged arrays
var ix = 0, iy = 0, iz = 0;         // indexes to the next element

// The following sorts the arrays in ascending sequence
x.sort(function(a, b){return a - b});
y.sort(function(a, b){return a - b});

while (ix < x.length || iy < y.length){     // while arrays x or y have elements

if (ix < x.length && iy < y.length){    // if both have elements, choose the lowest element

    if (x[ix] <= y[iy]){                // is the current element in array x less than the current element in y?
        z[iz] = x[ix];                  // choose x
        iz++;                           // point to the next space in z
        ix++;                           // ditto x
    } else{                             // choose y
        z[iz] = y[iy];                  
        iz++;                           // next
        iy++;                           // next
    }

} else if (ix < x.length){              // if only one has elements is it x?
    for (ix; ix < x.length; ix++){      // if so, move the rest of x to z
        z[iz] = x[ix];                  // copy current element in x
        iz++;                           // next z ... no need to increment x because the for loop does it
    }

} else if (iy < y.length){              // if only y has elements
    for (iy; iy < y.length; iy++){      // move the rest of y to z
        z[iz] = y[iy];                  // copy
        iz++;                           // increment z's pointer
    }
}
}

// display the resulting merged elements in the web page
var result = "<ul>";
for (var i in z){
    result += "<li>" + z[i] + "</li>"
}
result += "</ul>"
document.getElementById("placeAnswerHere").innerHTML=result;

/*
Things to think about:
. This code is hard wired to merge only 2 arrays
. You will need to create an array containing all arrays to be merged. e.g. q = [x, y, z, w, and more]
. Your loop will need to find the smallest element in any of the arrays in q and move it to z (the resultant array)
. There is a method shift() to strip the first element from an array (e.g. x.shift(); removes the first element in array x)
. This is like making a pile of cafeteria trays from a variable numbers of tray stacks.
. Remember to sort all arrays first
*/

So my new question becomes, how to accomplish this without writing a bunch of spaghetti code?

You need to merge all arrays into one array remove the dupilicates and then sort low to high correct? — Darkrum
– Darkrum, Commented Oct 11, 2016 at 23:32
If you have a merge(a, b) function that works with two arrays, you can trivially extend it to four arrays by doing merge(a, merge(b, merge(c, d))). If you have arbitrary many arrays, use a loop. — Bergi
– Bergi, Commented Oct 11, 2016 at 23:40
OP can you post in a edit this supposed merge tool that was developed in class. — Darkrum
– Darkrum, Commented Oct 11, 2016 at 23:59
Thank you but it should have been a separate code block while still keeping the original you posted. But WOW i reaffirm my earlier comment of your teacher being really stupid. — Darkrum
– Darkrum, Commented Oct 12, 2016 at 0:19

cpugourou · Accepted Answer · 2016-10-12 00:01:10Z

1

the fastest and shortest I can think of (unduplication bonus added):

var x = [5, 1, 0], y = [2, 5, 0], z = [78, 3, 1], w = [4, 34];

function sortNumber(a,b) {
    return a - b;
}
function uniq(a) {
   return Array.from(new Set(a));
}

var d = uniq(x.concat(y,z,w).sort(sortNumber));
/* [0, 1, 2, 3, 4, 5, 34, 78] */

edited Oct 12, 2016 at 0:01

answered Oct 11, 2016 at 23:38

cpugourou

7917 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

13 Comments

Darkrum Over a year ago

Ah! You beat me to it... Also OP your teacher is supid. Like really stupid.

cpugourou Over a year ago

the most important rule to follow whatever language you use is to avoid spaghetti codes. This is one of the best spaghetti code I have ever seen. In my world your teacher would be fired immediately to teach such stupid stuff.

Darkrum Over a year ago

The task is not stupid. What's stupid is the teachers lack of understanding of code. Remember this teacher is modeling the future gen of engineers... Would you want them on your team?

Ethan Morris Over a year ago

aha he is really nice tho!

Bergi Over a year ago

@cpugourou Yes, the code the OP has posted is bad, but as far as I understood it's his code not the teacher's one?

|

rcgldr · Accepted Answer · 2016-10-12 02:05:44Z

0

Although cpugourou's answer works, it doesn't appear to match the stated HW assignment. As for the HW assignment, one issue not clear to me is how to create a generic array of arrays (like for(i = 0; i < n; i++) aa[i] = new Array(...) ), which seem to conflict with the HW problem statement that the arrays are hard coded test cases.

Ignoring the issue of how to create generic array of hard coded arrays, once you do have an array of sorted arrays, the HW assignment appears to want you to implement an n way merge using the array of arrays. This means finding which array in the array of arrays has the smallest element and moving that element to the output array (append to output array, remove from the input array). When one of the n arrays is emptied, that array is removed from the array of arrays and you continue with an n-1 way merge. Repeate this until only 1 array remains, where the remainder of that last array is just copied (or moved) to the output array.

A common optimization for a n way merge is to use a heap, but I doubt you're expected to use a heap for this HW assignment.

edited Oct 12, 2016 at 2:05

answered Oct 12, 2016 at 1:54

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

2 Comments

Darkrum Over a year ago

The HW assignment is still bogus and the code is horrid and the teacher is still stupid. OP will probably still get a F because the teacher's ego will be hurt when he realizes his stuck in the past But then again that's how most university CS classes are.

rcgldr Over a year ago

@Darkrum - n way merges, usually utilizing a heap, are fairly common for external sorts, such as gnu sort which first creates a set of sorted temporary files, then repeated performs 16 way merges on the temporary files until a final merge that produces the sorted output file.

Collectives™ on Stack Overflow

How to merge sorted arrays within arrays into a third sorted array

2 Answers 2

13 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

13 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related