6 2 9 5 4 1 3In 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)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 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)
2 6 5 4 1 3 9Notice 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.
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
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.
function ShowArray(msg,theList)Then I could use a different caption for each display line. Try writing and running your own code, before looking at my solution.
for (var i=0; i<theList.length; i++) msg = msg + " " + theList[i];
This code creates the array and adds the first couple records:
var MusicData = ;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.
MusicData = "\t001\tMessiah\tHandel,G.\t1742/04/13"
+ "\tMormon Tab\tclassic\tMy all-time favorite";
MusicData = "\t002\t9th Symphony\tBeethoven,L.\t1824/05/07"
+ "\tLondon Phil\tclassic\t";
At the end of our musical database program we could display the whole list:
for (var ix=0; ix<MusicData.length; ix++)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 itemI also could have used the built-in String method split(delim) to extract the desired item:
var here = -1;
var thar = -1;
var base = 0;
if (indx<0) break; // found back of item
if (indx==0) here = thar+1; // front of desired item
base = thar+1;
thar = theLine.indexOf(delim,base);
if (thar<0) break;
if (here<0) return "";
if (thar<0) return theLine.substr(here);
function ItemOf(theLine,indx,delim) // returns indx'th itemMost interesting programming problems have multiple ways to solve them. Here is my sort function:
var ary = theLine.split(delim); // makes an array
function SortBy(theData,byKey)This is now called by a single line before the display loop to choose the sort key, in this example, by title:
var aLine = "";
for (var ix=theData.length-1; ix>=0; ix--)
aLine = theData[ix];
theData[ix] = ItemOf(aLine,byKey,"\t") + aLine;
for (ix=theData.length-1; ix>=0; ix--)
aLine = theData[ix];
theData[ix] = aLine.substr(aLine.indexOf("\t")+1);
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
Real Soon Now I hope to do another page on the programming techniques I used.
Rev 2010 December 23