Hour 9. Programming Algorithms
In this hour, you will learn about programming algorithms that are common across all programming languages. An algorithm is a common procedure or methodology for performing a certain task. In mathematics, algorithms provide step-by-step methods for solving a problem in a finite number of steps that can require some repetition. To keep things simple, you’ll see the algorithms in JavaScript, but the concepts you learn here are important no matter which programming language you use.
You will learn how to use your programs to count data values and accumulate totals. This is a technique that’s been touched upon in earlier lessons, but this hour will formalize your understanding of the topic. The computer is a perfect tool for counting values such as the number of customers in a day, month, or year or the number of inventory items in a department’s warehouse. Your computer also is capable of lightning-fast accumulations of totals. You can determine the total amount of a weekly payroll or the total amount of your tax liability this year.
Computers are masterful at sorting and searching for data. When you sort data, you put it in alphabetical or numerical order. There are different methods for doing this, and this hour presents the most common one. There are also many ways to search a list of data for a specific value. You might give the computer a customer number, have it search a customer list, and then have it return the full name and account balance for that customer. Although computers are fast, it takes time to sift through thousands of data items, especially when searching through disk files (your disk is much slower than memory). Therefore, it behooves you to gain some insight into some efficient means of performing a search.
After you master the sorting and searching techniques, this hour finishes by taking a topic you were introduced to in the last lesson and going a bit further with it—functions.
The highlights of this hour include:
Counting with counter variables
Storing data in array variables
Totaling with accumulator variables
Swapping the values of two variables
Understanding ascending and descending sorts
Using the bubble sort
Searching for values in unsorted lists
Searching by the binary search
Using functions to divide the jobs in your program
Nesting loops to improve a program’s effectiveness
Counters and Accumulators
When you see a statement such as the following, what do you think?
number = number + 1
Your first impression might be that the statement isn’t possible. After all, nothing can be equal to itself plus one. Take a second glance, however, and you will see that in a programming language such as JavaScript, the equal sign acts like a left-pointing arrow. The assignment statement, in effect, says “Take whatever is on the right side of the equal sign, evaluate it, and put it in the variable to the left of the equal sign.” Most of the other programming languages also use assignment statements that work like the JavaScript assignment.
When JavaScript reaches the statement just shown, it adds 1 to the contents in the variable named number. If number is equal to 7 to begin with, it is now equal to 8. After it adds the 1 and gets 8, it then stores 8 in number, replacing the 7 that was originally there. The final result is one more than the initial value.
When you see a variable on both sides of an equal sign, and you are adding 1 to the variable, you are incrementing that variable’s value. You might remember from earlier listings that adding 1 to a variable is useful. Many programmers put such an assignment statement inside a loop to count items. The variable used is called a counter. Every time the loop repeats, 1 is added to the counter variable, incrementing it. When the loop finishes, the counter variable has the total of the loop.
JavaScript (and other programming languages like C) have several ways to add 1 to a variable, and you’ve seen most of them already. Each of the following three statements add 1 to the variable count:
count = count + 1;
count += 1;
count++;
When adding 1, the third is the most efficient, but it can only be used to add 1. The first two choices can add any number to your variable—you just need to change the 1 to the number you’d like to add. That includes integers or floating point numbers. You can also add a variable in that spot as well, as the following line of code would add newAmount to count:
count += newAmount;
Subtracting 1 is just as easy. Again the following three statements all subtract 1 from the variable count, and again you can use the first two to subtract any number by replacing the 1 with that number:
count = count – 1;
count -= 1;
count--;
Try it Yourself
LISTING 9.1 A number-guessing game can use a counter variable.
<! DOCTYPE html>
<html>
<head>
<title>Guessing Game</title>
</head>
<body>
<script>
// Filename guessinggame.html
// Generates a random number between 1 and 100
// keeps getting guesses until the user is
// correct.
var compNum = Math.floor(Math.random()*100)+1;
var tries = 0;
alert("IT'S THE GUESSING GAME!");
alert("I am thinking of a number from 1 to 100");
do {
guess = prompt("What do you think the number is?");
if (guess < compNum) {
document.write(guess+" is too low! Try again");
document.write("<br>");
}
else if (guess > compNum) {
document.write(guess+" is too high! Try again");
document.write("<br>");
}
tries++;
} while (guess != compNum);
alert("You guessed the number in "+tries+" guesses!");
</script>
</body>
</html>
Array Variables
Anytime you find yourself writing two or more sets of statements and the only differences are the variable names, you are probably not taking advantage of a better programming style. The program to check grades that you wrote in Hour 6, “Controlling Your Programs,” was far more effective because you used arrays for both the names of the students and their test scores.
Tip
Another advantage to using an array for a set of similar variables is that you can take advantage of the powerful loop statements you learned in Hour 6. The goal of programming is to make your life simpler, not harder. Whenever you can put repetitive code into a loop, you save wear and tear on your fingers.
Reserving Array Space
In many programming languages, you declare arrays the same way you declare other variables—you just need to add brackets to the name with the size of the array (how many elements) between the brackets. This is not the case with JavaScript. As you may remember from Hour 6, you declare an array in JavaScript by calling the new Array() method. The following line of code declares an array named customers:
var customer = new Array();
If you know the size of the array you need, you can put that number inside the parentheses:
var MonthlySales = new Array(12);
You can also initialize the array’s elements by including them in the array call:
var Months = new Array("January", "February", "March");
Although this example would create a three-element where Months[0] is equal to "January", Months[1] is equal to "February", and Months[2] is equal to "March". If you wanted an array with all the months specified, you’d have to list them, or you could create a 12-element array and then fill the names in later.
LISTING 9.2 This sales program stores data in arrays for each month.
<! DOCTYPE html>
<html>
<head>
<title>Sales Report</title>
</head>
<body>
<script>
// Filename monthlysales.html
// program gets sales for each month
// and then prints out the monthly totals
var months = new Array(12);
var monthSales = new Array(12);
months[0] = "January";
months[1] = "February";
months[2] = "March";
months[3] = "April";
months[4] = "May";
months[5] = "June";
months[6] = "July";
months[7] = "August";
months[8] = "September";
months[9] = "October";
months[10] = "November";
months[11] = "December";
for (i = 0; i < 12; i++)
{
checker = "What were sales for the month of ";
checker += months[i];
monthSales[i] = prompt(checker);
}
for (i = 0; i < 12; i++)
{
document.write(months[i]+"'s sales were $");
document.write(monthSales[i]+"<br>");
}
</script>
</body>
</html>
Figure 9.2 shows the results of running Listing 9.2.
Parallel Arrays
The months and sales totals demonstrate a popular use of arrays. The months[] and monthSales[] arrays are known as parallel arrays. That is, the arrays each have the same number of elements, and each element in one corresponds to an element in the other.
With parallel arrays, you can store arrays with any type of data. Although a single array can hold only one type of data, you can have several parallel arrays that correspond to each other on a one-to-one basis. Using parallel arrays, you can keep track of an entire set of names, addresses, phone numbers, and salaries in a payroll program.
Accumulators for Total
An accumulator is similar to a counter in that the same variable name appears on both sides of the equal sign. Unlike counter variables, accumulators usually add something other than 1 to the variable. Use accumulators for totaling dollar amounts, sales figures, and so forth. You can use a total to expand on the monthly sales program and produce total yearly sales and average monthly sales for the bottom of the report.
To compute an average, you must accumulate the monthly sales, adding one at a time to an accumulator (the totaling variable). Because an average is based on the total number entered, you must also count the number of sales entered. After all the sales are entered, the program must divide the total amount of the sales by the total number of months. This produces an average. The program in Listing 9.3 shows you how to do this. The counting and accumulating processes shown in this program are used frequently in data processing, regardless of the programming language you use.
LISTING 9.3 A sales-reporting and averaging program can use an accumulator for sales totals.
<! DOCTYPE html>
<html>
<head>
<title>Sales Report</title>
</head>
<body>
<script>
// Filename salesreport.html
// program gets monthly sales totals and then
// calculates total sales and average per month
var months = new Array(12);
var monthSales = new Array(12);
months[0] = "January";
months[1] = "February";
months[2] = "March";
months[3] = "April";
months[4] = "May";
months[5] = "June";
months[6] = "July";
months[7] = "August";
months[8] = "September";
months[9] = "October";
months[10] = "November";
months[11] = "December";
var totalSales = 0;
for (i = 0; i < 12; i++)
{
checker = "What were sales for the month of ";
checker += months[i];
monthSales[i] = prompt(checker);
// Add the monthly sales to the totalSales
// Use parseFloat to ensure it's treated
// like a number
totalSales += parseFloat(monthSales[i]);
}
for (i = 0; i < 12; i++)
{
document.write(months[i]+"'s sales were $");
document.write(monthSales[i]+"<br>");
}
document.write("<p>Total sales for the year are $");
document.write(totalSales+"<br>");
var avgSales = totalSales/12;
document.write("Average monthly sales are $");
document.write(avgSales+"<br>");
</script>
</body>
</html>
Figure 9.3 shows the results of running Listing 9.3.
Swapping Values
The cornerstone of any sorting algorithm is data swapping. As you sort data, you have to rearrange it, swapping higher values for lower values. As Figure 9.4 shows, swapping values simply means replacing one variable’s contents with another’s and vice versa.
Suppose you assigned two variables named variable1 and variable2 with the following statements:
variable1 = 65;
variable2 = 97;
The concept of swapping them is simple. How would you do it? If you said the following, you would not quite be correct:
variable1 = variable2;
variable2 = variable1;
Can you see why these two assignment statements don’t swap the values in the two variables? The first statement assigns variable2 to variable1, which wipes out variable1’s original value. The second statement is then redundant because both variables already hold the same value after the first statement.
An accurate approach to swapping variables is to use a third variable, often called a temporary variable because you don’t use its value once you swap the original variables. Here is the code to perform the swapping accurately:
temp = variable1;
variable1 = variable2;
variable2 = temp;
Sorting
The following list of numbers isn’t sorted:
10
54
34
21
23
Here is the list sorted in ascending order (from lowest to highest):
10
21
23
34
54
Here is the list sorted in descending order (from highest to lowest):
54
34
23
21
10
You can also sort character string data, such as a list of names. Here is a list of five sorted names (unless otherwise specified, an ascending sort is always used):
Adams, Jim
Fowler, Lisa
Kingston, William
Stephenson, Mike
Williams, Pete
Using the Bubble Sort
There are several ways to sort lists of data. The most popular one for beginning programmers is called the bubble sort. The bubble sort isn’t the most efficient sorting algorithm. As a matter of fact, it is one of the slowest. However, the bubble sort, unlike other sorting algorithms (such as the heap sort and the quick sort) is easy to understand and to program.
The data that you want to sort is typically stored in an array. Using the array subscripts, you can rearrange the array elements, swapping values until the array is sorted in the order you want.
In the bubble sort, the elements of an array are compared and swapped two at a time. Your program must perform several passes through the array before the list is sorted. During each pass through the array, the bubble sort places the lowest value in the first element of the array. In effect, the smaller values “bubble” their way up the list, hence, the name bubble sort.
After the first pass of the bubble sort (controlled by an outer loop in a nested for loop, as you will see in the following program), the lowest value of 10 is still at the top of the array (it happened to be there already). In the second pass, the 21 is placed right after the 10 and so on until no more swaps take place.
Analyzing the Bubble Sort
To give you a better understanding of the bubble sort routine used in this program, Figure 9.5 shows you a flowchart of the bubble sort process. By using the flowchart and by following the program, you should be able to trace through the bubble sort and better understand how it works. At the heart of any sorting algorithm is a swapping routine, and you can see one in the body of the bubble sort’s for loops.
Tip
If you want a descending sort, you only have to change one statement in Listing 9.4’s program—the first statement inside the for loops. Instead of swapping the values if the second item of the pair is lower, swap them if the second item of the pair is higher. The new line looks like this:
if (values(ctr) < values(ctr + 1))
Searching Arrays
There are many methods for searching arrays for a specific value. Suppose you have several parallel arrays with inventory data. The first array, partNo[], holds all your inventory item part numbers. The second array, desc[], holds the description of each of those parts. The third array, price[], contains the price of each corresponding part. You might keep all the inventory data on the disk and then read that data into the parallel arrays when it is time to work with the data.
One use for an inventory program that uses parallel arrays is a look-up routine. A user could type a part number, and the computer program would search the partNo[] array for a match. When it finds one (for example, at element subscript number 246), you could then print the 246th element in the desc[] and price[] arrays, which shows the user the description and price of the part number just entered.
There are several ways to search an array for values. The various searching methods each have their own advantages. One of the easiest to program and understand, the sequential search, is also one of the least efficient. The search method you decide on depends on how much data you expect to search through and how skilled you are at understanding and writing advanced searching programs. The next few sections walk you through some introductory searching algorithms that you might use someday in the programs you write.
Performing the Sequential Search
The sequential search technique is easy but inefficient. With it, you start at the beginning of the array and look at each value, in sequence, until you find a value in the array that matches the value for which you are searching. (You then can use the subscript of the matching element to look in corresponding parallel arrays for related data.)
Tip
The array being searched doesn’t have to be sorted for the sequential search to work. The fact that sequential searches work on unsorted arrays makes them more useful than if they required sorted arrays because you don’t have to take the processing time (or programming time) to sort the array before each search.
Figure 9.6 shows a flowchart of the sequential search routine (as with most flowcharts in this hour, only the sequential search routine is described, not the now-trivial task of filling the array with data through disk input/output [I/O] or user input). Study the flowchart and see if you can think of ways to improve the searching technique being used.
Performing the Binary Search
If your array is already sorted, there is another technique that offers tremendous searching speed advantages over either of the sequential searches shown in the previous sections. This technique is known as the binary search. The binary search is more complex to understand and program than the sequential search, but, as with most things in the programming world, it is worth the effort in many cases.
The binary search technique uses a divide-and-conquer approach to searching. One of the primary advantages of the binary search is that with every comparison you make, you can rule out one-half of the remaining array if a match isn’t found. In other words, if you are searching for a value in a 100-element array, and the first comparison you make fails to match, you only have at most 50 elements left to search (with the sequential search, you would still have a possible 99 elements left to search). On the second search, assuming there is no match, you rule out one-half of the remaining list, meaning that there are only 25 more items to search through.
The multiplicative advantages of a binary search will surprise you. If you have a friend write down a number from 1 to 1,000 and then use the binary search technique to make your guesses (your friend will only have to tell you if you are “too low” or “too high” with each guess), you can often zero in on the number in 5 to 15 tries. This is an amazing feat when there is a pool of 1,000 numbers to choose from!
The binary search technique is simple. Your first guess (or the computer’s first try at matching a search value to one in the list) should be exactly in the middle of the sorted list. If you guess incorrectly, you only need to know if you were too high or low. If you were too high, your next guess should split the lower half of the list. If you were too low, you should split the higher half of the list. Your new list (one-half the size of the original one) is now the list you split in the middle. Repeat the process until you guess the value.
Suppose your friend thinks of the number 390. Your first guess would be 500 (half of 1,000). When your friend says “too high,” you would immediately know that your next guess should be between 1 and 499. Splitting that range takes you to your second guess of 250. “Too low,” replies your friend, so you know the number is between 251 and 499. Splitting that gives you 375. “Too low” means the number is between 376 and 499. Your next guess might be 430, then 400, then 390 and you’ve guessed it. One out of 1,000 numbers, and it only took six guesses.
Listing 9.6 uses the binary search technique to find the correct inventory value. As you can see from the code, a binary search technique doesn’t require a very long program. However, when you first learn the binary search, it takes some getting used to. Therefore, the flowchart in Figure 9.7 will help you understand the binary search technique a little better.
LISTING 9.6 A binary search can speed searching tremendously.
// Filename: searchbin.html
// Binary search for an item's description and price.
// (This assumes the arrays have been filled
// and SORTED in PartNum order elsewhere.)
// This code would be part of a larger inventory program.
// ** This program assumes that the variable named TotalNumber
// contains the total number of items in the inventory,
// and therefore, in the arrays as well.
// First, get the part number the user wants to look up
searchPt = prompt("What is the number of the part you want to see?");
first = 0; // Set the lower bound of your search
last = TotalNumber – 1; // The upperbound of the search
found = 0; // The flag that the part was found
while (first <= last)
{
mid = Math.floor((first + last) / 2) // Set the middle and make it an int
if (searchPt == PartNo[mid])
{
document.write("Part number "+searchPt+"'s description is ");
document.write(Desc[mid]+"<br>");
document.write("With a price of $"+price[mid]);
found = 1; // Turn the flag on
break; // Exit the while loop
}
else if (searchPt < PartNo[mid]) // Check the lower half of the array
last = mid - 1;
else
first = mid + 1 // Check the upper half of the array
}
if (found == 0) // The part was not in the array
{
document.write("<p>");
document.write("** Sorry, but that part number is not in the inventory.");
}
Taking Functions Further
Introduced in Hour 6, user-created functions deserve a bit more discussion. A function is like a detour; it is a side trip your program makes for a few statements, often accomplishing a specific task, and then the program gets back on the path it was executing and continues from there.
The function is a set of code that works as a unit, as a method works. Functions (also called subroutines in some programming languages) are available for all languages, and aren’t difficult to understand. The algorithms presented in this hour make perfect candidates for functions. A function turns your program into a collection of modules that you can integrate. Instead of one long program, your program becomes lots of little sets (functions) of code.
Understanding the Need for Subroutines
Suppose you’re writing a program that prints your name and address several times. Without using a function, you would write code similar to the snippet shown in Listing 9.7. The program repeats the same printing code over and over.
LISTING 9.7 A program outline that doesn’t use functions can be hard to maintain.
// Long program that prints name and address throughout
// (The rest of the code is not shown.)
// Program statements go here
document.write("Mark Cunningham<br>");
document.write("1244 West Oak<br>");
document.write("Canton, NH 63443<br>");
// More program statements go here
document.write("Mark Cunningham<br>");
document.write("1244 West Oak<br>");
document.write("Canton, NH 63443<br>");
// More program statements go here
document.write("Mark Cunningham<br>");
document.write("1244 West Oak<br>");
document.write("Canton, NH 63443<br>");
// More program statements go here
document.write("Mark Cunningham<br>");
document.write("1244 West Oak<br>");
document.write("Canton, NH 63443<br>");
// Rest of program finishes up here
Caution
Not only is repeating the same code tedious, but by requiring more typing, it lends itself to errors. If you only have to type in the code once, but can still execute that code repeatedly whenever you want (as in a function), your chances of typing errors decrease. Also, if your address ever changes, you only have to change it in one place (inside the subroutine), not everywhere it appears in the program.
If you put the document.write statements in a function, you would save yourself some typing. It would also be easier to transfer the code to another program. All you have to do is write the function and then call it as often as you’d like.
Listing 9.8 is an improved version of the previous program outline. Notice that a statement begins the subroutine’s name and address printing code. This is a label that you make up that names the subroutine’s location.
LISTING 9.8 A program outline that uses functions is simple.
<! DOCTYPE html>
<html>
<head>
<title>Function Example</title>
<script>
function printAddress() {
document.write("Mark Cunningham<br>");
document.write("1244 West Oak<br>");
document.write("Canton, NH 63443<br>");
}
</script>
</head>
<body>
<script>
// Long program that prints name and address throughout
// (The rest of the code is not shown.)
// Program statements go here
printAddress(); // Runs the function
// More program statements go here
printAddress(); // Runs the function
// More program statements go here
printAddress(); // Runs the function
// More program statements go here
Tip
As mentioned is Hour 6, you can put your commonly used functions in a separate .js file that you can then add to any .html file that needs to use that function.
By asking users how many numbers they want to enter, the program has far more value than a program that can only sort a set number of values. Printing the numbers before and after the sort shows the value of functions, as you’ve called the function twice in the program, but only had to write the code once.
Nested Loops
As with almost all statements, you can nest two or more loops inside one another. Several listings in this hour have done just that, including Listing 9.9. As a programmer, you must make sure you understand the concept of nested loops. Anytime your program needs to repeat a loop more than once, use a nested loop. Think of the inside loop as looping “faster” than the outside loop. The inside loop iterates faster because the counter variable of the inside loop goes through all its iterations before the outside loop’s first iteration has completed. Because the outside loop doesn’t repeat until its block of code is complete. When the outside loop finally does iterate a second time, the inside loop starts all over again.
So if you have an outer loop that is set to run 5 times, and an inner loop that is set to run 10 times, the inner loop executes a total of 50 times. The outside loop iterates five times, and the inside loop executes 10 times for each of the outer loop’s iterations.
Summary
The techniques you learned in this hour will be useful throughout your entire programming career. Sorting, searching, and functions are needed for useful data processing. The computer, thanks to your programs, can do these mundane tasks while you concentrate on more important things.
The next hour gives you a break from algorithms and shows you how to write some programs that use graphics. Programming can be fun and graphics are quite possibly the most fun part of programming.
Q&A
Q. How do functions improve a program’s accuracy?
A. A program is easier to write and maintain when you group routine code together in functions. The functions help you focus on specific parts of the program that you need to change or fix if bugs exist in the code. When your whole program is comprised of small routines, in functions, you make your code more modular and you help ensure that code in one part of the program doesn’t affect code in another part of the program.
Quiz
1. What is an accumulator?
2. True or false: The following statement is an accumulator statement:
num = num - 1
3. What is the difference between the terms ascending sort and descending sort?
4. Why is a third variable needed when you want to swap the values of two variables?
5. Which sort is the easiest to write and understand?
6. True or false: A counter statement is a special kind of accumulator statement?
7. What is the simplest kind of search technique?
8. Which is more efficient: the binary search or the sequential search?
9. Write a function that takes a number, doubles it, adds 2, and returns the new value.
10. True or false: Using functions saves typing the same code over and over throughout a program.
Answers
1. An accumulator is a variable whose value is updated.
2. False. Although the statement might actually be using an accumulator variable, the statement happens to be decreasing the value stored there, whereas accumulators are usually added to.
3. An ascending sort puts lists in order from low to high and a descending sort puts lists in order from high to low.
4. The third variable is needed to hold one of the values temporarily.
5. The bubble sort is one of the simplest sorts to write and understand.
6. True.
7. A sequential search is the simplest search technique.
8. The binary search is far more efficient than the sequential search.
9. Again, your execution may be slightly different:
function changenumber(x)
{
var y = x * 2;
z = y + 2;
return (z);
}
10. True.