An introduction to searching and sorting techniues

Sorting is an important concept that is extensively used in the fields of computer science. Sorting is nothing but arranging the elements in some logical order.

For example, we want to obtain the telephone number of a person, if the telephone directory is not arranged in a alphabetical order, one has to search from the very first page to till the last page. If the directory is sorted, we can easily search for the telephone number.

Sorts are generally classified as either internal or external sorts 

An internal sort is a sort in which all of the data are held on primary memory during the sorting process.

An external sort uses primary memory for the data currently being sorted and secondary storage for any data that will best fit in primary memory.

Basic / General sorting concepts

Sort order: Data may be sorted in either ascending sequence or descending sequence. The sort order identifies the sequence of the sorted data, ascending or descending. If the order if the sort is not specified, it is assumed to be ascending order.

Sort stability: Sort stability is an attribute of a sort indicating that the data which equal keys maintain their reactive input order in the output.

Sort efficiency: It is a measure of the reactive efficiency of a sort. It is usually an estimate of the number of comparisons and moves required to order an unordered list.

Pass: During the sorting process, the data are transferred many times. Each traversal of the data is refereed to as a sort pass. Depending on the algorithm, the sort pass may traverse the whole list or just a section of the list.

Searching:

searching means to find whether a particular value is present in the array or not. If the value is present in the array then searching is said to be successful and the searching process gives the location of that value on the array, otherwise, if the value is not present in the array, the searching process displays the appropriate message and in this case searching is said to be unsuccessful.

There two types searching techniues 

1. Linear search or sequential search

2. Binary search