Quick Sort and Merge Sort Techniques
Sorting Techniques
 Quick Sort Bubble Sort Hash or Address Calculation Sort

Working of Quick Sort

• In each step of quick sort a range of an array is sorted.
• The first element in the range is used as the pivot value.
• The rest of the values in the range are grouped into two partitions: one containing the values larger than the pivot value and the other containing the values smaller than the pivot value.
• Each of the partions is sorted by a recursive call of quick sort.
• The partitioning of a range of values proceeds as follows.
• The index ' i ' is used to find a value that cannot be included in the partition of smaller values.
• The index ' j ' is used to find a value that cannot be included in the partition of larger values.
• The value that cannot be included in the partition of smaller values and the value that cannot be included in the partition of larger values are exchanged.
• The above two steps are repeated until all the values in the range are divided into the two partitions.
• Finally, the pivot value is moved between the two partitions.

Initial Step - First Partition

Sort Left Partition in the same way

Difference between Quick Sort and Merge Sort

• In Merge Sort,the splitting is trivial (simply taking two halves) and the joining is hard (merging the two sorted files).
• In Quick Sort,the splitting is hard (Partitioning) and the joining is trivial (the two halves and the pivot automatically form a sorted array).
• Quick Sort is an Inplace Sort Algorithm.(i.e., it doesn't require additional temporary space to store elements as they sort,they use the space originally occupied by the elements).
• Merge Sort is not an Inplace Algorithm.

Source Code of :

## Working of Bubble Sort

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 :

## Address Calculation Sort or Hash Sort

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) =====>
 12 null
F(2) =====>
 25 null
F(3) =====>
 33
=====>
 37 null
F(4) =====>
 48 null
F(5) =====>
 57 null
F(6)

=

null
F(7)

=

null
F(8) =====>
 86 null
F(9) =====>
 92 null

Source Code of :