Bigger JavaScript Examples


This page continues the tutorial on learning programming using JavaScript. Here we discuss some examples of JavaScript, in increasing complexity. First is an extended discussion on sorting, with a practical example of sorting text data. In the next page we try a couple games. Finally we do a really esoteric computer science task, actually interpreting JavaScript in JavaScript. It's a head-scratcher even for most professionals, but you can understand it with a little effort.
 

Sort Example

Programs spend a lot of time sorting data. Don Knuth's monumental classic The Art of Computer Programming (he never got to volume 4 until just recently) devoted half of volume 3 to sorting. For a while programmers competed to see who could write the fastest sort algorithm (an algorithm is a well-defined, step-by-step way to solve a mathematical problem). Mathematically, the fastest a sort can go is "NlogN", the logarithm of the number of records to sort times the number of records. The logarithm of a number is roughly the number of digits it takes to write that number. In base 10, logarithm of 10 is 1 (because it has a single zero), log10(100) is 2 (two zeros), 1000 is 3, and so on. Computers think in binary, and the 2-base log of a binary number is approximately the number of bits: log2(2) is 1, log2(4) is 2, log2(8) is 3, and so on. It's a simple multiplier to convert one to another, so which base you are working with doesn't make a lot of difference. NlogN (calculated in base 10) is 10 when N is 10, 200 when N=100, 3000 for N=1000. Large sorts take more time than just a multiplier on the number of records.

The fastest sorts are really messy to understand, and since the problem was essentially solved more than 30 years ago, they are not much fun nor value to learn. JavaScript has a built-in sort function which probably uses one of those fast algorithms. We will do a much simpler but slower N2 algorithm, the bubble sort. Consider a sequence of unsorted numbers:

6  2  9  5  4  1  3
In your mind, if you wanted to sort them, you might look for the smallest number and move it to the front. Then go back and look for the next smallest number and put it second, and so on. Thinking about how you would solve a problem is often a good first step in writing a program to do it, but there are several performance problems with this first cut. To find the smallest number, you need to walk through the whole list. You can't stop when you get to the 1, because there might be something smaller. There isn't, which you can see at a glance, but you have a God's-eye view and the computer does not.

It gets worse. Now you want to move that 1 to the front of the list. The list is typically in an array, and the first position is already taken with a 6, which you must somehow displace, either by moving everything over, or else by exchanging it with the 1. Exchanging is the basis of the faster sorts, but knowing what to exchange without walking through the whole list each time is the key. Our simplistic bubble sort doesn't do any searching at all, it just looks at the first two numbers, and if they are out of sequence, exchanges them. Then it looks at the second and third numbers (now 6 and 9) and if they are out of sequence, exchanges them. And so on up to the end of the list, like this:

6  2  9  5  4  1  3 (start)
2  6  9  5  4  1  3  (after first exchange)
2  6  5  9  4  1  3  (after second exchange)
2  6  5  4  9  1  3
2  6  5  4  1  9  3
2  6  5  4  1  3  9  (at end of first pass)
Notice that the list of numbers is still unsorted, but the 9 is in the right position. You should run through the list yourself now and verify that four more passes each leave the numbers a little more sorted:
2  6  5  4  1  3  9
2  5  4  1  3  6  9
2  4  1  3  5  6  9
2  1  3  4  5  6  9
1  2  3  4  5  6  9
Notice that each pass "bubbles" the next higher number to its place near the top. If the numbers were exactly backwards to start with, it would take N-1 passes of N-1 tests (and possible exchanges) to get them right, slightly under N2 tests total.

Now, how to do this in JavaScript? Start with our unsorted list of numbers:

var theList = [6,2,9,5,4,1,3];
You need two nested loops. The inner loop indexes through the list, comparing each item to the next, and exchanging them if necessary. Can you write that? We happen to know that this list has seven elements, but you should use theList.length so that it works for any size list. Remember, for a list of length 7, you are doing only six compares. Now you can wrap another loop around that. Most bubble sorts use a boolean variable xchd which is initially false at the beginning of the outer loop, and set to true whenever an exchange is made. If you get to the end of the inner loop with no exchanges, you are done. I prefer to just run the inner loop N-1 times, where N is the length of the array.

To exchange two array elements, you will need to copy one of them into a temporary variable, then move the other into it, then finally put the temporary into the second element thus freed up. You may need to sprinkle logging output liberally throughout your code. I wrote a function to display the whole array:
function ShowArray(msg,theList)
{
  for (var i=0; i<theList.length; i++) msg = msg + " " + theList[i];
  document.write(msg);
}
Then I could use a different caption for each display line. Try writing and running your own code, before looking at my solution.
 

Using Text Sort

Sorting numbers is not very useful. More often you have some data with several different elements (think of our Music collection in the previous page), and you want them in a particular order, typically by one of the fields. If the records are sorted by artist, then it would be easy to find all the songs by a particular artist. On another occasion you might be interested in a chronological order.

In a suitably OOPS language (C++ or Java) doing a Music class would be straight forward, and we would discuss here how to sort objects. But let's implement it instead as a text file with one line for each song. JavaScript was designed to have minimal input and output capabilities (to make it harder for rogue web pages to steal private data from your computer, which is a good thing), so we will need to build the collection in code and display it on our test page.

First we need to design the record format. The usual horizontal separator for tabular elements is the horizontal tab key, which we can insert into a string using the text escape code '\t'. Another text escape '\n' (for newline) separates the records. Different operating systems use respectively newline or return ('\r') or both together as a line separator in text files, but within our own program we can use any separators we like. On each line, the first field will be a variable sort key, followed by a tab, then a unique record number representing the order the item was entered in the database, another tab, then the actual data: first the title (and another tab), then the composer, then the date composed or first performed, the artist (singer or performer) name, genre, and finally a comments field. Each line will have eight fields separated by seven tab characters, and be stored in one array element. Let's call the array MusicData. We will use the built-in JavaScript MusicData.sort() method to sort the elements by whatever key we choose to put in the first field.

This code creates the array and adds the first couple records:

var MusicData = [];
MusicData[0] = "\t001\tMessiah\tHandel,G.\t1742/04/13"
    + "\tMormon Tab\tclassic\tMy all-time favorite";
MusicData[1] = "\t002\t9th Symphony\tBeethoven,L.\t1824/05/07"
    + "\tLondon Phil\tclassic\t";
The text is too long for one code line, so I split it using the concatenate operator. Notice that I have left the sort key empty; we will fill that in programmatically. The entry number has a couple zeros in front, so if I ever decide to sort by it, #5 will come before #12. A textual sort compares the first character against the first character, and 5 is higher than 1. Similarly, I put the year first in the date, and inserted leading zeros in the month and day to make sorts on the date come out right. Names are similarly stored last name first. Your tastes may run into different musical styles, so you'd have other values in each of your data.

At the end of our musical database program we could display the whole list:

for (var ix=0; ix<MusicData.length; ix++)
  document.write(MusicData[ix]+"<p>");
You can run this much, and it will display your whole collection in accession order. It gets more interesting if you insert  code to sort it by a particular field. I wrote a function to copy the sort key to the first field, sort it, then remove the key for display. This required a second function to extract that key from the line:
function ItemOf(theLine,indx,delim) // returns indx'th item
{
  var here = -1;
  var thar = -1;
  var base = 0;
  while (true)
  {
    if (indx<0) break; // found back of item
    if (indx==0) here = thar+1; // front of desired item
    indx--;
    base = thar+1;
    thar = theLine.indexOf(delim,base);
    if (thar<0) break;
  }
  if (here<0) return "";
  if (thar<0) return theLine.substr(here);
  return theLine.substr(here,thar-here);
}
I also could have used the built-in String method split(delim) to extract the desired item:
function ItemOf(theLine,indx,delim) // returns indx'th item
{
  var ary = theLine.split(delim); // makes an array
  return ary[indx];
}
Most interesting programming problems have multiple ways to solve them. Here is my sort function:
function SortBy(theData,byKey)
{
  var aLine = "";
  for (var ix=theData.length-1; ix>=0; ix--)
  {
    aLine = theData[ix];
    theData[ix] = ItemOf(aLine,byKey,"\t") + aLine;
  }
  theData.sort();
  for (ix=theData.length-1; ix>=0; ix--)
  {
    aLine = theData[ix];
    theData[ix] = aLine.substr(aLine.indexOf("\t")+1);
  }
}
This is now called by a single line before the display loop to choose the sort key, in this example, by title:
SortBy(MusicData,2);
For an exercise, suppose you only wanted to display the songs by a particular artist, or with a date limited to a single year. How would you do that? Try it yourself, before looking at my solution. Yours may be different, but if it works correctly, that's OK. You need to be creative.

Next: Some games
 
 

JavaScript Interpreter

My favorite litmus test for programming, a really awesome JavaScript example program, is a JavaScript interpreter written in JavaScript. The language can handle it, but there seems to be no good way to get a script into the program as data. Which is a good thing for what JavaScript is intended for. You don't want virus code -- that's what web page scripts are, code that you did not invite into your computer, snuck into your computer without your knowledge or permission, and running on your computer doing stuff you mostly would not consent to if they asked -- you don't want virus code poking around in your data. So JavaScript input methods are rather weak.

See Using the JavaScript Interpreter for more information.

Real Soon Now I hope to do another page on the programming techniques I used.

Tom Pittman
Rev 2010 December 23