Sorting refers to ordering or rearranging of data in an increasing or decreasing fashion according to some linear relationship among the data items.
A collection of records called a list where every record is having one or more fields. The fields which contains unique value for each record, is termed as the key field. For example, a phone number directory can be thought of as a list where each record has three fields - 'name' of the person, 'address' of those person, and their 'phone numbers'. Being unique phone number can work as a key to locate any record in the list.
Sorting is the operation performed to arrange the records of a table or list in some order according to some specific ordering criterion. Sorting is performed according to some key value of each record.
The records are either sorted either numerically or alphanumerically. The records are then arranged in ascending or descending order depending on the numerical value of the key.
The techniques of sorting can be divided into two categories. These are:
Internal Sorting: If all the data that is to be sorted can be adjusted at a time in main memory, the internal sorting method is being performed.
External Sorting: When the data that is to be sorted cannot be accommodated in the memory at the same time and some has to be kept in auxiliary memory such as hard disk, floppy disk, magnetic tapes etc, then external sorting methods are performed.
Various sorting techniques are analyzed in various cases and named these cases as follows:
Hence, the result of these cases is often a formula giving the average time required for a particular sort of size 'n'. Most of the sort methods have time requirements that range from O(nlog n) to O(n2).
A collection of records called a list where every record is having one or more fields. The fields which contains unique value for each record, is termed as the key field. For example, a phone number directory can be thought of as a list where each record has three fields - 'name' of the person, 'address' of those person, and their 'phone numbers'. Being unique phone number can work as a key to locate any record in the list.
Sorting is the operation performed to arrange the records of a table or list in some order according to some specific ordering criterion. Sorting is performed according to some key value of each record.
The records are either sorted either numerically or alphanumerically. The records are then arranged in ascending or descending order depending on the numerical value of the key.
Categories of Sorting:
- Internal Sorting
- External Sorting
Internal Sorting: If all the data that is to be sorted can be adjusted at a time in main memory, the internal sorting method is being performed.
External Sorting: When the data that is to be sorted cannot be accommodated in the memory at the same time and some has to be kept in auxiliary memory such as hard disk, floppy disk, magnetic tapes etc, then external sorting methods are performed.
Sorting Efficiency:
There are many techniques for sorting. Implementation of particular sorting technique depends upon situation. Sorting techniques mainly depend on two parameters. First parameter is the execution time of program, which means time taken for execution of program. Second is the space, which means space taken by the program.
Most of the sorting techniques are data sensitive and so the metrics for them depends on the order in which they appear in an input array.
Various sorting techniques are analyzed in various cases and named these cases as follows:
- Best case
- Worst case
- Average case
Hence, the result of these cases is often a formula giving the average time required for a particular sort of size 'n'. Most of the sort methods have time requirements that range from O(nlog n) to O(n2).
Types of Sorting Techniques:
- Bubble Sort
- Selection Sort
- Merge Sort
- Insertion Sort
- Quick Sort
- Heap Sort
No comments:
Post a Comment