1. Use the merge function to write a sorting algorithm. This has to be in HTML f
ID: 3809182 • Letter: 1
Question
1. Use the merge function to write a sorting algorithm. This has to be in HTML format with some javascript in it The algorithm is as follows:
function newsort(array):
if array length <= 1:
// an array of length 1 is already sorted
return array
else:
// divide the array in half, sort them separately
// and then merge them back together
mid = middle index of array
left = a new array of size mid
right = a new array of size array length – mid
copy leftmost elements of array into left
copy rightmost elements of array into right
left = newsort(left)
right = newsort(right)
result = merge(left, right);
return result
2. Verify that the sorting algorithm above actually sorts some data. Then profile the new sorting algorithm and compare it against the other sorting algorithms you have studied. Produce a plot similar to that given in the key points that shows the relationship between the time it takes to sort and the number of elements in the array. The following functions should help you with this problem:
// build an array of random data to sort
function makeRandomArray(size)
{
var result = Array();
while (size > 0)
{
result.push(Math.floor(Math.random()*100000));
--size;
}
return result;
}
// time the sorting algorithm on the given array, in milliseconds
function timeSortingAlgorithm(arr, sortingAlgorithm)
{
var startTime = new Date()
sortingAlgorithm(arr);
var endTime = new Date();
return endTime.getTime() - startTime.getTime();
}
Here is what I have so far.
HTML
<html>
<head>
<title>Array Sort</title>
<script src="newsort.js" language="JavaScript" type="text/javascript"></script>
</head>
<body>
<h4>New sorted array:</h4>
<script>
var randomArray = [4, 3, 2, 1];
document.writeln("randomArray: " + randomArray + "<br />");
var sortedArray = newsort(randomArray);
document.writeln("sortedArray: " + sortedArray + "<br />");
</script>
</body>
</html>
and the javascript
function newsort(array){
if (array.length <= 1) {
// an array of length 1 is already sorted
document.writeln("At 1: " + array + "<br />");
return array
}
else {
// divide the array in half, sort them separately
// and then merge them back together
var mid = (array.length / 2);
var left = new Array(mid.length);
var end = (array.length - mid.length);
var right = new Array(end.length);
newsort(left)
newsort(right)
result = merge(left, right);
document.writeln("result: " + result + "<br />");
}
return result
}
function merge(ar1, ar2){
tlength = ar1.length + ar2.length;
//this new array sets the length of the new array to total both arrays being merged
arr3 = new Array(tlength);
firstcounter = 0;
secondcounter = 0;
for (i = 0; i < arr3.length; i++) {
// this if else statement decides whether to take next smallest number from
// first array or second.
if ((secondcounter == ar2.length) ¦¦
((firstcounter < ar1.length) &&
(ar1[firstcounter] < ar2[secondcounter]))) {
arr3[i] = ar1[firstcounter];
firstcounter++;
}
else {
arr3[i] = ar2[secondcounter];
secondcounter++;
}
}
return arr3;
When i run my code, the arrays do not show up in the html :(
Explanation / Answer
there were several syntax errors in your code, I have fixed them (Note: I added the code for javascript file in html itself):
<html>
<head>
<title>Array Sort</title>
<script>
function newsort(array){
if (array.length <= 1) {
// an array of length 1 is already sorted
document.writeln("At 1: " + array + "<br />");
return array
}
else {
// divide the array in half, sort them separately
// and then merge them back together
var mid = (array.length / 2);
var left = new Array(mid.length);
var end = (array.length - mid.length);
var right = new Array(end.length);
newsort(left)
newsort(right)
result = merge(left, right);
document.writeln("result: " + result + "<br />");
}
return result
}
function merge(ar1, ar2){
tlength = ar1.length + ar2.length;
//this new array sets the length of the new array to total both arrays being merged
arr3 = new Array(tlength);
firstcounter = 0;
secondcounter = 0;
for (i = 0; i < arr3.length; i++) {
// this if else statement decides whether to take next smallest number from
// first array or second.
if ((secondcounter == ar2.length) ||
((firstcounter < ar1.length) &&
(ar1[firstcounter] < ar2[secondcounter]))) {
arr3[i] = ar1[firstcounter];
firstcounter++;
}
else {
arr3[i] = ar2[secondcounter];
secondcounter++;
}
}
return arr3;}
</script>
</head>
<body>
<h4>New sorted array:</h4>
<script>
var randomArray = [4, 3, 2, 1];
document.writeln("randomArray: " + randomArray + "<br />");
var sortedArray = newsort(randomArray);
document.writeln("hahaaaa");
document.writeln("sortedArray: " + sortedArray + "<br />");
</script>
</body>
</html>
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.