Searching, Merging and Sorting
SEARCHING
To search a file means to scan it methodically looking for a given item. The simplest method of searching is a linear search. A linear search is one in which each record is read in turn and checked for the item. If the end of the file is reached without finding the required item then the search has failed.
Word processor and editor programs allow the user to search for a word in a passage of text, and to replace it with another word if necessary .
File enquiry packages are available which allow the user to search a file for items or combinations or selected items .
Example
The following is part of a file detailing the name and colouring of cat breeds.
|
Name |
Colour 1 |
Colour 2 |
Colour 3 |
Eyes |
|
Birman |
Blue |
Chocolate |
Blue |
|
|
Blue-cream long-hair |
Blue |
Cream |
Orange |
|
|
Blue Persian |
Blue |
Orange |
||
|
British Blue |
Blue |
Orange |
||
|
Brown Burmese |
Brown |
Yellow |
||
|
Calico |
Black |
Red |
Cream |
Orange |
|
Chinchilla |
White |
Green |
||
|
Havana Brown |
Brown |
Green |
An enquiry program is used to find the names of cats with certain colour combinations.
1 The search pattern : Colour 1 = Brown
produces the names: Brown Burmese, Havana Brown
2 The search pattern : (Colour 2 = Cream OR Colour 3 = Cream) and (Eyes = Orange) produces the names: Blue-cream long-hair and Calico
MERGING
Two files are merged by interleaving their records to form one file which still has its records in order.
A common example of merging is when two sequential files have their records in order and they have to be combined into a single file (see worked question below).
Example of a situation where files would be merged
A firm selling car parts has a master file of all the stock. Details of each part are stored in one record with the part number as key item. The file is stored sequentially in the order of the part numbers. When a new car model is introduced a file detailing all its parts is supplied to the firm. This file is then merged with the existing master file to produce a new file which includes parts for the new car.
SORTING
To sort data means to arrange it into order. Usually alphabetical data is sorted into alphabetical order and numbers into ascending order.
Files are sorted because:
1 File operations on two or more files are simpler if the files are in the same order (see updating and merging).
2 An operation on a serial file may be easier if the keys are in order (e.g. searching for a record if the key is known).
3 People reading files printed out on paper find them easier to use if they are in order.
Worked question
For the two files A and B, the first item of each record is to be taken as the key by which they are sequenced. The files are:
File A
256023 A.F.SMITH 234.56
403214 J.P.JONES 156.25
207888 L.C.JACKSON 2478.00
365142 P.JONES 89.50
File B
864512 P.R.TAYLOR 105.23
956421 A.FREEMAN 325.20
125642 S.ARBER 1025.60
320147 P.R.WEBER 68.25
403215 M.PALMER 512.00
Show the result of:
1 sorting the two files into correct sequence,
2 merging the sorted files.
1 File A when sorted is:
207888 L.C.JACKSON 2478.00
256023 A.F.SMITH 234.56
365142 P.JONES 89.50
403214 J.P.JONES 156.25
File B when sorted is:
125642 S.ARBER 1025.60
320147 P.R.WEBER 68.25
403215 M.PALMER 512.00
864512 P.R.TAYLOR 105.23
956421 A.FREEMAN 325.20
2 The two files when merged give:
125642 S.ARBER 1025.60
207888 L.C.JACKSON 2478.00
256023 A.F.SMITH 234.56
320147 P.R.WEBER 68.25
365142 P.JONES 89.50
403214 J.P.JONES 156.25
403215 M.PALMER 512.00
864512 P.R.TAYLOR 105.23
956421 A.FREEMAN 325.20
SORTING SEQUENTIAL FILES
In a computer, data can only be sorted when it is in the main store. Usually a file is too large to store all at once in the main store.
Such a file can be sorted as follows:
1 The file is read into the main store, a group of records at a time.
2 Each group is sorted and written back onto the backing store.
3 When all the groups have been sorted, they are merged again to produce a completely sorted file.
METHODS OF SORTING DATA IN THE MAIN STORE
A set of data items can be sorted into order by many methods. The methods below have been described for numbers, but can also be used to sort names and other strings.
Insertion
Build up a new set of numbers by taking each number in turn and inserting it into its correct place in the new set.
Selection
Search through the set, select the smallest and place it first. Then search again to find the next smallest, place it second and so on until they have all been selected.
Exchange
1 Compare two of the numbers to see if they are in the correct order.
2 if they are, leave them alone; if not, exchange them.
3 Carryon until all the numbers are in the correct order.
BUBBLE SORT
A bubble sort is an exchange sort in which a number is always compared for possible exchange with the one next to it in the set.