[EN book] Cookbook-Sorting and Searching Algorithm.pdf

(158 KB) Pobierz
Sorting and Searching Algorithms:
Sorting and Searching Algorithms:
A Cookbook
Thomas Niemann
Preface
This is a collection of algorithms for sorting and searching. Descriptions are brief and intuitive,
with just enough theory thrown in to make you nervous. I assume you know C, and that you are
familiar with concepts such as arrays and pointers.
The first section introduces basic data structures and notation. The next section presents
several sorting algorithms. This is followed by techniques for implementing dictionaries ,
structures that allow efficient search , insert , and delete operations. The last section illustrates
algorithms that sort data and implement dictionaries for very large files. Source code for each
algorithm, in ANSI C, is available at the site listed below.
Permission to reproduce this document, in whole or in part, is given provided the original
web site listed below is referenced, and no additional restrictions apply. Source code, when part
of a software project, may be used freely without reference to the author.
T HOMAS N IEMANN
Portland, Oregon
email :
home :
By the same author:
A Guide to Lex and Yacc, at http://members.xoom.com/thomasn/y_man.htm .
- 2 -
162356994.001.png
CONTENTS
2.1
Insertion Sort
8
2.2
Shell Sort
10
2.3
Quicksort
11
2.4
Comparison
14
3.1
Hash Tables
15
3.2
Binary Search Trees
19
3.3
Red-Black Trees
21
3.4
Skip Lists
25
3.5
Comparison
26
4.1
External Sorting
29
4.2
B-Trees
32
- 3 -
1. Introduction
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.
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].
0
4
Lb
1
7
2
16
3
20
M
4
37
5
38
6
43
Ub
Figure 1-1: An Array
int function SequentialSearch (Array A , int Lb , int Ub , int Key ) ;
begin
for i = Lb to Ub do
if A [ i ] = Key then
return i ;
return –1 ;
end;
Figure 1-2: Sequential Search
- 4 -
162356994.002.png
int function BinarySearch (Array A , int Lb , int Ub , int Key ) ;
begin
do forever
M = ( Lb + Ub )/2;
if ( Key < A[M] ) then
Ub = M – 1;
else if (Key > A[M]) then
Lb = M + 1;
else
return M ;
if (Lb > Ub) then
return –1;
end ;
Figure 1-3 : Binary Search
If the data is sorted, a binary search may be done (Figure 1-3) . Variables Lb and Ub keep
track of the lower bound and upper bound of the array, respectively. We begin by examining the
middle element of the array. If the key we are searching for is less than the middle element, then
it must reside in the top half of the array. Thus, we set Ub to ( M – 1) . This restricts our next
iteration through the loop to the top half of the array. In this way, each iteration halves the size
of the array to be searched. For example, the first iteration will leave 3 items to test. After the
second iteration, there will be one item left to test. Therefore it takes only three iterations to find
any number.
This is a powerful method. Given an array of 1023 elements, we can narrow the search to
511 elements in one comparison. After another comparison, and we’re looking at only 255
elements. In fact, we can search the entire array in only 10 comparisons.
In addition to searching, we may wish to insert or delete entries. Unfortunately, an array is
not a good arrangement for these operations. For example, to insert the number 18 in Figure 1-1,
we would need to shift A [3]… A [6] down by one slot. Then we could copy number 18 into A [3] .
A similar problem arises when deleting numbers. To improve the efficiency of insert and delete
operations, linked lists may be used.
- 5 -
162356994.003.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin