Page 263 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 6. L < R

7. SWAP (A,3,8) to get
0 1 2 3 4 5 6 7 8 9
A[] = A D D A O U R M Y N
8 A [4] = ‘O’ > V, There fore, L = 4
9. A[7] = ‘M’ < V, There fore, R = 7

10. L < R
11. SWAP (A,4,7) to get

0 1 2 3 4 5 6 7 8 9
A[] = A D D A M U R O Y N

12. A [5] = ‘U’ > V;.. L = 5
13. A[4] = ‘M’ < V;R = 4
14. L < R ,.. break
15. SWAP (A,5,9) to get.

0 1 2 3 4 5 6 7 8 9
A[] = A D D A M N R O Y U
at this point ‘N’ is in its correct place.
A[5], A[0] to A[4] constitutes sub list 1.
A[6] to A[9] constitutes sublist2. Now

16. Quick sort (A, 0, 4)
17. Quick sort (A, 5, 9)
The Quick sort algorithm uses the O(N Log N) comparisons on average. The performance can be
2
improved by keeping in mind the following points.
1. Switch to a faster sorting scheme like insertion sort when the sublist size becomes
comparatively small.
2. Use a better dividing element I in the implementations. We have always used A[N] as the
dividing element. A useful method for the selection of a dividing element is the Median-of
three method.
Select any 3 elements from the list. Use the median of these as the dividing element.

12.8 Bucket Sort

Bucket sort runs in linear time on the average. It assumes that the input is generated by a random
process that distributes elements uniformly over the interval [0, 1].
The idea of Bucket sort is to divide the interval [0, 1] into n equal-sized subintervals, or buckets,
and then distribute the n input numbers into the buckets. Since the inputs are uniformly
distributed over (0, 1), we don’t expect many numbers to fall into each bucket. To produce the
output, simply sort the numbers in each bucket and then go through the bucket in order, listing
the elements in each.
The code assumes that input is in n-element array A and each element in A satisfi es 0 ≤ A[i] ≤ 1.
We also need an auxiliary array B[0 . . n -1] for linked-lists (buckets).

258 LOVELY PROFESSIONAL UNIVERSITY