Algorithms halt in a finite amount of time

Algorithms should be composed of a finite number of operations and they should complete their execution in a finite amount of time. Suppose we wanted to write an algorithm to print all the integers greater than 1. Our steps might look something like this:

1. Print the number 2.
2. Print the number 3.
3. Print the number 4.
   .
   .
   .

While our algorithm seems to be pretty clear, we have two problems. First, the algorithm must have an infinite number of steps because there are an infinite number of integers greater than one. Second, the algorithm will run forever trying to count to infinity. These problems violate our definition that an algorithm must halt in a finite amount of time. Every algorithm must reach some operation that tells it to stop.

When writing algorithms, we have several choices of how we will specify the operations in our algorithm. One option is to write the algorithm using plain English. An example of this approach is the directions to John's house given in the introduction lesson. Although plain English may seem like a good way to write an algorithm, it has some problems that make it a poor choice. First, plain English is too wordy. When we write in plain English, we must include many words that contribute to correct grammar or style but do nothing to help communicate the algorithm. Second, plain English is too ambiguous. Often an English sentence can be interpreted in many different ways. Remember that our definition of an algorithm requires that each operation be unambiguous.

Another option for writing algorithms is using programming languages. These languages are collections of primitives (basic operations) that a computer understands. While programming languages avoid the problems of being wordy and ambiguous, they have some other disadvantages that make them undesirable for writing algorithms. Consider the following lines of code from the programming language C++.

This algorithm sums the numbers from 1 to 10 and displays the answer on the computer screen. However, without some special knowledge of the C++ programming language, it would be difficult for you to know what this algorithm does. Using a programming language to specify algorithms means learning special syntax and symbols that are not part of standard English. For example, in the code above, it is not very obvious what the symbol "++" or the symbol "<<" does. When we write algorithms, we would rather not worry about the details of a particular programming language.

What we would really like to do is combine the familiarity of plain English with the structure and order of programming languages. A good compromise is structured English. This approach uses English to write operations, but groups operations by indenting and numbering lines. An example of this approach is the directions for changing motor oil in the introduction lesson. Each operation in the algorithm is written on a separate line so they are easily distinguished from each other. We can easily see the advantage of this organization by comparing the structured English algorithm with the plain English algorithm.

For the remainder of this study, we will write our algorithms using the structured English approach. Now that we have a definite way of writing our algorithms, let's look at some algorithms for solving the problem of sorting. Sorting is a very common problem handled by computers. For example, most graphical email programs allow users to sort their email messages in several ways: date received, subject line, sender, priority, etc. Each time you reorder your email messages, the computer uses a sorting algorithm to sort them. Since computers can compare a large number of items quickly, they are quite good at sorting.

There are three different algorithms for sorting: the Simple Sort, the Insertion Sort, and the Selection Sort. The sorting algorithms share two basic operations in common. These operations are the comparison operation and the swap operation.

Date: 2015-12-17; view: 849