Homework 10 Help
HW10 #1
The homework provides the algorithm for implementing a new sorting algorithm in pseudo-code. This pseudo-code needs to be turned into JavaScript. This is a recursive algorithm -- a function that callsitself, since no repetition loops are in the p-code neither should there be any in your JavaScript. The p-code asks you to create 2 new arrays, a left and a right array. Do not get hung up on creating code to accomplish this. First, investigate the methods (functions) that arrays can perform. I was able to create each new array in one line of code. I suggest looking through the documentation that will return a piece of an array for you (perhaps the .slice method)
Here are some popular questions I have been asked from previous terms.
Q. What is it that we are supposed to do by having the newsort function call itself?
A: The first call the newsort receives the entire original array. Then the array is split in half and newsort is called again (recursively) to sort the left and right portions. On those 2 second calls, the 1/2 arrays are split in to again (now 1/4 arrays) and newsort is called to sort the 1/4 left and right portions. Eventually it gets down to left and right side arrays of length = 1 and it all "unwinds" and returns a left and right arrays that are sorted. Then the merge function is called to put the 2 portions of the current call to newsort together. This keeps happening until it gets back up to the original call to newsort and the merge will put together the two 1/2 size arrays into a sorted array of the original array and returns it.
Q. If it does call itself, how many times or perhaps the better question is - what is the control mechanism we are supposed to use?
A: The control mechanism is the true portion of the if statement at the beginning of the pseudo code. Eventually the array gets divided down to an array of one element and the array is returned. This allows all the other recursive calls to newsort to continue and eventually get to the true portion of the if statement.
Q: Based on the pseudo code we are given, I don't see any indication of looping but maybe that is implied. Perhaps if I understood the answer to my first question it would all be clear...
A: There isn't any explicit looping. The recursion of calling newsort provides the splitting of the pieces of the array until the array gets sorted.
HW10 #2
You should recreate (in a spreadsheet) the table in the course web site - Figure12.5, for the 3 sorts covered - insertion, selection, and bubble at the different array sizes (or elements) noted in column 1. This is necessary because the current information in the table is very old and not done on your computer. Next, you should gather the same msec data values for your newsort() function and put them in a new column at the right after the last sort. Then use the Excel functionality to plot a bar graph showing the 4 sort speeds -- insertion, selection and bubble, and newsort.
The words "compare it" in #2 isvery important. I'll belooking for a cell in the spreadsheetwhere you've typed a aparagraph or two telling me what you think of the speeds of the sort. Topics to consider include:
· which is fastest? (personally, my computer was so fast , I had to bump up the number of elements in each of the arrays in order to get timing values that weren't 0ms.)
· which is slowest?
· why do you think the fastest is the fastest? (This is an excellent question that should be considered a few minutes before answering too quickly)
· why do you think the slowest is the slowest?
· does the ranking of speed as you expect? Why?
· any other comparisons you think of!
This is the only assignment you will turn in that has not only HTML and JS file(s) but will have a spreadsheet in the ZIP file also.
Here are some popular questions I have been asked from previous terms.
Q: Hello! I am a little confused about what my JavaScript file should contain for homework 10 part 2. I am thinking the the file should contain the code provided on the homework document and all three types of sorts from your sort.js example file correct. Do I just run one sort at a time and comment the other two out or do make the JavaScript file so it runs all three of the sorts ( one after the other).
A: Yes, all the functions in the Word document are used in the example test runs I gave in the email, so they need to be included in your JS file.
You also need my sort.js and a reference to it in the HTML head tag so you can call the sort functions. Technically you don't call the sort functions directly, you pass the function names as the second parameter to the timing function (timeSortingAlgorithm).
I chose to run all the sorts in a row and then copy down the timing information. Then I modified all the sizes to the random array for each sort to be larger. Then you write down those results. Then you put all your data in Excel, a plot a graph. Then I'm expecting everyone to draw some conclusions about the speed of the sort functions.
Q: What needs turned in for part 2 of this assignment? I had an excel spreadsheet with numbers filled out accordingly to what the profiling showed. I used code to get my answers and then input them into a spreadsheet. Is that incorrect? When I got this email I followed the following instructions and changed my code to follow your format. I was just alerting to my screen and copying the milliseconds to my excel spreadsheet. The assignment is very vague as far as how the second part needs to be presented or shown.
A: What you said in your email does sound very close. With the possible exception that you are supposed to profile the sorts again yourself on your computer. That was why I helped out with the sorts.js file and the email on how to call them. From your question, I think you did this correctly but I want to make sure that you wrote JavaScript code to call the sorts for profiling and did not presume some numbers based upon the chart in the key points or recitation.
All I'm looking for is that you profiled the sorts and called them, gathered profile information, and put it in an Excel spreadsheet. Then you should draw some conclusions. Does your computer support or refute what the chart in the Key Points says? It would be a good idea to include your Excel spreadsheet XLS file in your ZIP file submission.