Searching and sorting

Arrays

Figure 1-1 shows an array, seven elements long, containing numeric values. To search the array

sequentially, we may use the algorithm in Figure 1-2. The maximum number of comparisons is

7, and occurs when the key we are searching for is in A[6].

4

7

16

20

37

38

43

0

1

2

3

4

5

6 Ub

M

Lb

Arrays and linked lists are two basic data structures used to store information. We may wish to

search, insert or delete records in a database based on a key value. This section examines the

performance of these operations on arrays and linked lists.

Summary

As we have seen, sorted arrays may be searched efficiently using a binary search. However, we

must have a sorted array to start with. In the next section various ways to sort arrays will be

examined. It turns out that this is computationally expensive, and considerable research has been

done to make sorting algorithms as efficient as possible.

Linked lists improved the efficiency of insert and delete operations, but searches were

sequential and time-consuming. Algorithms exist that do all three operations efficiently, and

they will be the discussed in the section on dictionaries.

Sorting

Several algorithms are presented, including insertion sort, shell sort, and quicksort. Sorting by

insertion is the simplest method, and doesn’t require any additional storage. Shell sort is a

simple modification that improves performance significantly. Probably the most efficient and

popular method is quicksort, and is the method of choice for large arrays.