Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 791

Table 13.3 Algorithm Runtime Comparison Chart

Input
size ( N ) ( N 2 ) ( N 3 ) O(1) O(log N )O N ) ( N log N ) O(2 N )

100 100 ms 100 ms 100 ms 100 ms 100 ms 100 ms 100 ms

200 100 ms 115 ms 200 ms 240 ms 400 ms 800 ms 32.7 sec

400 100 ms 130 ms 400 ms 550 ms 1.6 sec 6.4 sec 12.4 days

800 100 ms 145 ms 800 ms 1.2 sec 6.4 sec 51.2 sec 36.5 million

years

4.21 * 10 24 1600 100 ms 160 ms 1.6 sec 2.7 sec 25.6 sec 6 min

49.6 sec years

5.6 * 10 61 3200 100 ms 175 ms 3.2 sec 6 sec 1 min 54 min

42.4 sec 36 sec years

Table 13.3 presents several hypothetical algorithm runtimes as the input size N
grows, assuming that each algorithm requires 100 ms to process 100 elements. Notice
that even though they all start at the same runtime for a small input size, as N grows the
algorithms in higher complexity classes become so slow that they would be impractical.
When you look at the numbers in Table 13.3, you might wonder why anyone bothers
to use O ( N 3 ) or O (2 N ), algorithms when O (1) and O ( N ) algorithms are so much
faster. The answer is that not all problems can be solved in O (1) or even O ( N ) time.
Computer scientists have been studying classic problems such as searching and sort-
ing for many years, trying to find the most efficient algorithms possible. However,
there will likely never be a constant-time algorithm that can sort 1,000,000 elements
as quickly as it can sort 10 elements.
For large datasets it's very important to choose the most efficient algorithms possi-
ble (i.e., those with the lowest complexity classes). Algorithms with complexity
classes of O ( N 2 ) or worse will take a long time to run on extremely large datasets.
Keeping this in mind, we'll now examine algorithms to search and sort data.

13.3 Implementing Searching and Sorting Algorithms

In this section we'll implement methods that search and sort data. We'll start by writing
code to search for an integer in an array of integers and return the index where it is
found. If the integer doesn't appear in the array, we'll return a negative number. We'll
examine two major searching algorithms, sequential and binary search, and discuss
the tradeoffs between them.
There are literally hundreds of algorithms to sort data; we'll cover two in detail in
this chapter. The first, seen later in this section, is one of the more intuitive algo-
rithms, although it performs poorly on large datasets. The second, examined as a case
study in the next section, is one of the fastest general-purpose sorting algorithms that
is used in practice today.