SORTING

1 Sorting

General Concepts

            A file is an ordered collection of items.Each item in the file is called a record. The records are named as r[1], r[2],…..r[n], where n is the size of the file.

            A key is associated with each record r[i] and through this key only we can identify the records in the file.

            Sorting is a process to arrange the records in the file in an order (either ascending or descending) with respect to the key. This can be classified into

i)                    Internal Sorting

ii)                  External Sorting

Internal sorting is defined as a sorting in which all records of the file to be sorted should be within the main memory at the time of sorting.

External sorting is defined as a sorting in which at the time of sorting some records of the file to be sorted can be in the secondary storage.

Example

            Let A be a list of  n elements a1, a2…….an. After sorting the list A in ascending order the numbers are rearranged as follows.

                  a1 ≤ a2 ≤ a3 ≤…..≤ an