|
Sorting files |
What is Sorting?
Sorting is arranging distinct objects in a pre-determined order. Quite often when we have a list of objects, we may need to sort them to make processing easier. For example, files in a folder are arranged alphabetically, or in order of their creation dates; topics in a book are arranged in increasing order of their page numbers in the list of contents. Books in a library are arranged alphabetically according to author's names; your phone directory or contacts list is arranged alphabetically. It would be very inconvenient for us if these items were not already sorted.
Different Types of Sorting
There are two major classifications for sorting in computer applications. They are classified on the basis of the size of files to be sorted. These two types are as follows :-
1. Internal Sorting
2. External Sorting
Internal Sorting
Internal Sorting is applicable for sorting items which are small enough to be easily accommodated in main memory. There are several sorting techniques in this category. Some of them are :-
1. Bubble Sort
5. Merge Sort
6. Heap Sort
7. Radix Sort
The minimum time complexity achievable by internal sorting is O(n logn). However, bubble sort, insertion sort and selection sort are of the order of O( n^2 ).
External Sorting
Often we have to deal with large databases with sizes greater than the optimum amount which can be stored in the main memory. In such a situation, some of the data has to be stored in some external storage device, such as external hard drives. In external sorting techniques, we also utilise functions that sort the data in optimum time. One of the most popular external sorting techniques is the Merge Sort algorithm. Some other external sorts include replacement selection method and polyphase merge sort method.
Wednesday 10 December 2014