Ethan Morris Ethan Morris - 1 month ago 7
Javascript Question

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

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: 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
*/

Answer

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] */
Comments