Divide And Conquer algorithm and Quicksort sorting

Tram Ho

1.Introduction

Divide and conquer is a method applicable to problems that can be solved by subdivide them into subproblems from solving these subproblems. Then the solutions of small problems are aggregated to solve the original problem. In short, it consists of three steps: division, rule, and union

The Quicksort algorithm is a featured algorithm as its name coined – quick sort. Quicksort has been selected in competitions for its efficiency, flexibility and ease of operation. The worst-case algorithm is O (n ^ 2) (worst-case) and its performance is, on average, O (nlogn). Quicksort, like Merge sort, applies a divide-and-conquer model.

2. Analysis

Here are three Quicksort processing steps for sorting a sub array A [l..r] (l – left for the first index, r – right for the last index).

Divide:

Divide array A [l..r] into 2 subarrays A [l..p-1] and A [p + 1..r] (p – pivot is the key index chosen for dividing the array, maybe index, trailing, mean or random). Arrays are allowed to be empty. So that the elements to the right of the pivot have a value greater than or equal to the pivot for the case of ascending (as opposed to descending) sort, the elements to the left of the pivot have a value less than or equal to the pivot. Calculating the pivot is part of this processing step.

Tri (Conquer):

Sort 2 subarrays A [l … p-1] and A [p + 1..r] by recursively calling the above function (recursive algorithm I put in the link attached below)

Combine:

Because the child arrays are sorted, there is no need to combine them.

The following is a code model of the implementation process

-Quicksort

To sort the entire array A, we initialize the Quicksort function (A, 1, A.length)

-Partition (division function)

Partition function above always selects the end of the array as the pivot (pivot_value = A [r]). When the function runs it will divide the array into 4 parts (the part may not contain any elements). After each sorting iteration, we get a new array with the following characteristics, for each element with any index k then:

– Illustrative example

3. Conclusion

Thus, we have learned and grasped the basic steps of Quicksort algorithm, when applying in practice, we need to adjust the input parameters to suit the intent of the problem. However, just by grasping the above 3 basic steps, we can solve most sorting problems. Hope you learn well.

References: Introduction to algorithm book

Share the news now

Source : Viblo