Sorting and Searching Notes

The operation of sorting is basically performed in business data-processing applications. Now become equally important in scientific applications.

Various sorting methods are available starting from basic algorithms like selection sort, bubble sort, linear sort and insertion sort to the more complex algorithms like quick sort, heap sort, and radix sort. Data structures like trees and queues are used to perform the sorting operations.

Notation and Concept:

  • Data can occur in any form and it is assumed that it is avi. as collection of elements. Each element is represented by a record which contains a number of information fields. These records are stored into a table which represents the information on which sorting is to be performed. Each field in the record contains alphanumeric information.

  • List of Sorting Technique
    • Selection sort
    • Bubble sort
    • Linear sort
    • Insertion sort
    • Quick sort
    • Heap sort
  • A table is assumed to be an ordered sequence of n records R1, R2,……., Rn. Each record contains one or more keys and processing is carried out with respect to these keys. We will assume that each record contains single key field and other additional information.
  • Sorting is the operation of arranging the records of a table into some sequential order according to an ordering criterion. The sort is performed according to the key value of each record and the records can be sorted either numerically or alphanumerically according to the type of key.
  • In numerical sorting records are arranged in ascending or descending order. In general key can be any sequence of characters but to simplify the process it is assumed that the key will be numeric.
  • Most of the sorting algorithms involve movement of the records from one place to another in the table. In certain applications records are quite long n really expensive to move, the records can be organized in such a manner as to minimize this moving cost while performing the sort.
  • One method of reducing the cost of moving the records is to arrange the table as a simple linked list. The movement of records is efficient when such a representation is used. The additional memory required for a pointer field becomes less significant as the record length increases.
  • Another method is to use a pointer vector, each element of which contains the address of one record. Fig. shows a small student record table according to grades before and after sorting. The shaded area in each record represents information such as name and course number.
Share

About the Author

Akash Padhiyar

Visit Website

There are no comments yet, add one below.

Leave a Comment

Your email address will not be published. Required fields are marked *

*

Time limit is exhausted. Please reload CAPTCHA.