Sorting Techniques |
|
Initial Step - First Partition
Sort Left Partition in the same way
Difference between Quick Sort and Merge Sort
Source Code of :
The Only redeeming features of the bubble sort are that it requires little additional space (one additional record to hold the temporary value for interchanging and several simple integer variables) and that it is O(n) in the case that the file is completely sorted (or almost completely sorted).This follows from the observation that only one pass of n-1 comparisions (and no interchanges) is necessary to establish that a sorted file is sorted.
Source Code of :
In this method a function f is applied to each key.The result of this function determines into which of several subfiles the record is to be placed.
The Program assumes an array of two-digit numbers and uses the first digit of each number to assign that number to a subfile.
For example,consider the sample file
25 | 57 | 48 | 37 | 12 | 92 | 86 | 33 |
Ten Subfiles are used,one for each of the possible first digits.Initially,each of these subfiles is empty.An array of pointers f[10] is declared,where f[i] points to the first element in the file whose first digit is i.After scanning the first element (25) it is placed into the file headed by f[2].Each of the subfiles is maintained as a sorted linked list of the original array elements.After processing each of the elements in the original file,the subfiles appear as shown below.
F(0) | = |
null | ||||||
F(1) | =====> |
|
||||||
F(2) | =====> |
|
||||||
F(3) | =====> |
|
=====> |
|
||||
F(4) | =====> |
|
||||||
F(5) | =====> |
|
||||||
F(6) | = |
null | ||||||
F(7) | = |
null | ||||||
F(8) | =====> |
|
||||||
F(9) | =====> |
|
Source Code of :
© Copyrights Madhu Sudan Rao G.K