Wall 4: Sorting and Searching in Arrays

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.


Summary of Basic Requirements

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.

Input Data Validation

As in all your programs, you will need to validate the user's input data. However, for this exercise, the user gives a word (a string) so fewer things can go wrong than with numeric data. Let's work with these restrictions:

Bubble Sort: Putting the Lexicon in 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.

Linear Search: Finding the Word

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".

Examples (Test Data)

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: yield
This 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)

Hints

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.