|
|
|
|
|
|
|
(text box continued from previous page) |
|
|
|
|
|
|
|
|
As you can see, for a list of over 1 billion values, BinSearch takes only 30 iterations. It is definitely the best choice for searching large lists. Algorithms such as BinSearch are said to be of logarithmic order. |
|
|
|
| |
|
|
|
|
Now let's turn to sorting. Function SelSort contains nested For loops. The total number of iterations is the product of the iterations performed by the two loops. The outer loop executes N-1 times. The inner loop also starts out executing N-1 times, but steadily decreases until it performs just one iteration: the inner loop executes N/2 iterations. The total number of iterations is thus |
|
|
|
| | |
|
|
|
|
Ignoring the constant factor and lower-order term, this is N2 iterations, and SelSort is an O(N2) algorithm. Consider that, whereas BinSearch takes only 30 iterations to search an ordered array of 1 billion values, putting the array into order takes SelSort approximately 1 billion times 1 billion iterations! |
|
|
|
| |
|
|
|
|
We mentioned that in a case study we would develop the technique of inserting values into an ordered list as they are input. In the meantime, we can consider the approach in the abstract. On average, Insert has to shift down half of the values (N)/2 in the list; thus, it is an O(N) algorithm. If Insert is called for each input value, we are executing an O(N) algorithm N times; therefore, sorting with insertion is and O(N2) algorithm. |
|
|
|
| |
|
|
|
|
Is every sorting algorithm O(N2)? Most of the simpler ones are, but O(N * log2N) sorting algorithms exist. Algorithms that are O(N * log2N) are much closer in performance to O(N) algorithms than are O(N2) algorithms. For example, if N is one million, then an O(N2) algorithm takes a million times a million (one trillion) iterations, but an O(N * log2N) algorithm takes only 20 million iterations-that is, it is 20 times slower than the O(N) algorithm but 50,000 times faster than the O(N2) algorithm. |
|
|
|
|
|
|
|
|
|
Now let's turn our attention to a second application of arrays-a special kind of array that is useful when working with alphanumeric data. |
|
|
|
|
|
|
|
|
Working with Character Strings |
|
|
|
|
|
|
|
|
In Chapter 2, we introduced string constants. Syntactically, a string constant is a sequence of characters enclosed by double quotes: |
|
|
|
|
|
|
|
|
A string constant is stored as a char array with enough components to hold each specified character plus one more-the null character. The null character, which is the first character in both the ASCII and EBCDIC character sets, has internal representation 0. In C++, the escape sequence \0 stands for |
|
|
|
|
|
