Sorting and Searching

SORTING AND SEARCHING

INTRODUCTION

Sorting and Searching are fundamental operations in computer science. Sorting refers to the operation of arranging data in an order. Searching refers to the operation of searching the particular record from the existing information.

Normally, the information retrieval involves searching, sorting and merging. In this chapter, we will discuss the searching and sorting techniques in detail. Sorting in general refers to various methods of arranging or ordering things (numerical, chronological, alphabetical, hierarchical etc.) based on criteria.

Sorting and Searching is one of the very common application for computers. For example the telephone company stores information such as the names, addresses and phone numbers of its customers. When you dial directory assistance to get the phone number for someone, the operator must look up that particular piece of information from among all of data that has been stored. Taken together, all of this information is one form of a database, which is organized as a collection of records. Each record consists of several fields, each containing one piece of information, such as the name, address, phone number, id number, etc.

The illustration given below shows how the sorting is performed.

The processes of looking up a particular data record in the database is called searching. As we will see, in order to do an efficient search in a database. the records must be maintained in some order. For example, consider the task of finding the phone number in the phone book of someone whose name you know, as opposed to trying to find the name of someone whose phone number you know in the same book.

As the amount of information to be stored and accessed becomes very large, the computer proves to be a useful tool to assist in this task. Over the years, as computers have been applied to these types of tasks, many techniques and algorithms have been developed to efficiently maintain and process information in data bases.

In this topic, we will develop and implement some of the simpler instances of sorting algorithms. Sorting and searching together constitute a major area of study in computational methods. We present some of these methods here to introduce this area of computing as well as to make use of some of the programming techniques