Sorting Techniques
Sorting is a process to arrange the records in the file in an order(either ascending or descending) with respect to the key.
Sorting can be divided into two types of categories called internal and external sorting based on location of records at the time of sorting.
The characteristics of sorting methods are – Data Sensitivity, Stability, Storage Requirements, Efficiency
Characteristics of Sorting methods
—————————————————-
- Data Sensitiveness
- Stability
- Storage Requirements
- Efficiency
Data Sensitiveness: The sorting methods for which the time to sort an array depends on the order in which the elements appear in the original array (i.e., Sorted or Unsorted). are called Data Sensitive Methods.
Stability: Methods that preserve the original ordering of elements are called stable methods.
Storage requirements: Minimal storage sorting methods are those methods that use minimal storage space by rearranging the elements with the space occupied by the original array.
Efficiency: Efficiency is the tome required to the array by any sorting method depending upon the number of comparisons required for that sorting method.
Types of Sorting
————————-
1. Bubble sort
2. Selection sort
3. Quick sort
4. Insertion sort
5. Merge sort
6. Heap sort
Bubble sort: This method works according to exchange sort technique,where the records are physically interchanged within the file according to their key values
Bubble sort is data sensitive. The number of checking required may be anything between 1 to (n-1) where ‘n’ denotes the number of elements in the array.
Quick sort: Fast method of internal sorting. Uses divide and conquer method of sorting
Insertion sort: Compares the elements of the array in the growing order successively.
Two variations of this insertion
Shuttle sort – Requires (n-1)rounds of checking if there are n elements in the array
Shell sort– Similar to the shuttle sort but sorts the arrays in the ascending order.
Merge Sort: Merging means combining two sorted arrays into single sorted array.
Steps in the process:
Scan both the arrays for right to left
Compare the first element of each array
The above step is repeated until one array is completely empty.
The remaining elements in the other array are stored in the merged array in the order as they were in.
Heap Sort: The value at each node in a heap (Binary tree)
is larger than the value at its existing children. The root contains the largest item.
