Data Structures and Algorithms/Sorting Data/Benefit of D&C

From Wikiversity
Jump to navigation Jump to search

Why dividing brings a benefit shall be demonstrated with QuickSort. We assume that we start with an algorithm with a quadratic characteristic. We make a general estimate about the time for a sort

T = K * n2

If we divide the data records into two groups of equal size in such a way that all elements of the first group are smaller than the ones of the second group, we get this timing:

T = K * (½ n)2 + K * (½ n)2
= ¼ K * n2 + ¼ K * n2
= ½ K * n2

Neglecting the time for the split operation, the sort is done with double speed. If we subdivide the groups of data records once more, we get

T = K * (¼ n)2 + K * (¼ n)2 + K * (¼ n)2 + K * (¼ n)2
= 4/16 K * n2
= ¼ K * n2

With any additional division by two the total effort for a sort is divided by two. How many times a group can divided by two, which is the number of recursion levels we get, can be calculated by help of the logarithm with radix two.

L = lg2 (n)

With the last division there is only one element left in each group and the quadratic characteristic disappears.

n2 = 12 = 1

On any of the division levels all the n data records have to be inspected (which subgroup does it belong to), therefor the time for a sort can be estimated by

T = M * n * lg2(n)

where M reflects the implementation and gives the time needed for the decision into which subgroup a record will go and to move it there.