It might help you follow the description of the program functionality while viewing the HTML template I have prepared for you to use on this program. If you right click on the web page you can view the HTML (view page source) and save it to your computer for editing.
You are given (as you see in the template) a "lexicon" of words. The user supplies you with a target word as input. You are to write a JavaScript program that will first sort the lexicon into alphabetic order (smallest first). Then the program will search for the target word in the lexicon using linear search. If the word is in the lexicon, the program will return the index in the array where it found the word; if the word is not in the lexicon, the program will return the error message "not found".
The lexicon is represented in JavaScript as an array of strings. Here is the variable declaration that appears in the code template:
var lexicon = [ "finally", "this", "default", "var", "class", "delete", "else", "break", "extends", "case", "false", "function", "debugger", "static", "try", "const", "if", "with", "in", "instanceof", "let", "new", "typeof", "package", "void", "implements", "return", "export", "public", "switch", "enum", "catch", "while", "super", "protected", "throw", "null", "interface", "do", "true", "yield", "continue", "private", "import", "for" ];This is a list of the reserved words in JavaScript; it is as good a list of words as any to use for this exercise. Notice the strings in the array are not in alphabetic order. Linear search will work on an unordered list, but ordering it will make the search a bit more efficient. So your first task in your program is to sort the array of strings into alphabetic order.
Sorting is a very important area of algorithm design. Bubble sort is one of the easiest to program and it works fine for small lists of items (arrays). However it is very inefficient and for large collections and the time needed to sort makes it impractical to use.
Your bubble sort function will need to have the lexicon passed in as an argument. You will rearrange the locations where many of the strings are stored to get them into order, and then the function will return the lexicon (the entire array will be sent back as return value).
Write the function in two pieces. First write a piece (it can be a helper function) that "bubbles up" the largest item in the array to the high end (to the location with the largest index). Do this by going through the array from index 0 to the end (by now you should be thinking for loop to access every item in an array in order). At each index i compare the item at i with the item at i+1. If they are out of order, swap them (remember the swap we discussed in class, which uses a temp variable).
Once you have the bubbleUp piece, you can then use it inside an outer loop so that it gets done one time for every item in the array. This will keep bubbling largest items upward until they are all in order. The name bubble sort comes from this repeated bubbling of the largest to the end.
Searching is another very important area of algorithm design. Linear searching is about the easiest way to look for an item in a collection (array). It is very easy to program and works fine for small collections. However it is inefficient and for very large collections the time needed to search makes it impractical to use.
Note: Do not do this by using the array indexOf function. I want you to write the code to actually go through the array looking for a match. The point of this assignment is to practice using arrays.
There is not much to say about how to code it up. Your function will need to have both the lexicon (array) and the target string passed in as arguments. Start with the first position in the array (index 0) and go up to the last index position the array. At each index, compare the string stored in the array with the target string. You are comparing it for equality (so use our new operator ===). If you find a string in the array that is the same as the target string, return the index where you found it. If you go through the entire array and do not find the target then the function returns the error message "not found".
Assuming you start with the lexicon shown above (the one in your program template), the array should look like this after it is sorted:
array "lexicon" 0: break 1: case 2: catch 3: class 4: const 5: continue 6: debugger 7: default 8: delete 9: do 10: else 11: enum 12: export 13: extends 14: false 15: finally 16: for 17: function 18: if 19: implements 20: import 21: in 22: instanceof 23: interface 24: let 25: new 26: null 27: package 28: private 29: protected 30: public 31: return 32: static 33: super 34: switch 35: this 36: throw 37: true 38: try 39: typeof 40: var 41: void 42: while 43: with 44: yieldThis sorted array is the one being used for the linear search. I do not want the array printed for the final results, but you certainly will want to print it out for your own debugging to be sure your code is working correctly.
Here are some (input/output) pairs then for the final results:
(instanceof, 22) (type, not found) (typeof, 39) (enum, 11) (yield, 44) (until, 42) (class, 3) (super, 33) (boolean, not found) (break, 0) (extra, not found) (for, 16)
Grow your program a little piece at a time. Do not type in 100 lines of code and then hope it works. It won't... and then you won't be able to easily find the line(s) that are causing the problem(s).
Instead, build an outline of the algorithm with comments. Then go back and convert each comment into a few lines of code. Then test the few lines you added, see if the program is doing what you expect it to be doing.
For loops allow you to access the items in an array systematically... from index 0 on up in order.
When you write a new function, write a stub. This is a function that doesn't do anything much other than announce that it is working (via alert, for example). You might then make the stub alert its argument(s) so you can see that the correct information is being passed in.
You might also have the stub return a "fake value" of the correct type, range, and format so that the rest of the program that is calling it can use the stub. This means that if the function supposed to compute and return some non-negative number, then just put in "return 1" so that it at least appears to be working.
Once it is all connected up correctly and running when called, you can go back and make it produce the correct results and replace the "fake return" with the correct return value.