Saturday, March 16, 2013

Searching. Merging and Sorting

Searching, Merging and Sorting

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.