DIVIDE & CONQUER ALGORITHM | QUICK SORT – SHOUT CODERS

15 Likes Comment
BinarySRCH

Divide and Conquer is an algorithmic pattern. In algorithmic methods, the design is to take a dispute on a huge input, break the input into minor pieces, decide the problem on each of the small pieces, and then merge the piecewise solutions into a global solution. This mechanism of solving the problem is called the Divide & Conquer Strategy.

Divide and Conquer algorithm consists of a dispute using the following three steps.
❖ Divide the original problem into a set of sub problems recursively.
❖ Conquer: Solve every sub problem individually.
❖ Combine: Put together the solutions of the sub problems to get the solution to the whole problem.

Quick Sort is also based on the concept of Divide and Conquer, just like merge sort. But in
quick sort all the heavy lifting(major work) is done while dividing the array into subarrays,
while in case of merge sort, all the real work happens during merging the subarrays. In case of
quick sort, the combine step does absolutely nothing.
It is also called partition-exchange sort. This algorithm divides the list into three main parts:

  1. Elements less than the Pivot element
  2. Pivot element(Central element)
  3. Elements greater than the pivot element

According to the Wikipedia page on Quick sort, this qualifies as an in-place algorithm, as the algorithm is just swapping elements within the input data structure.

Quick Sort is an unstable algorithm because we do swapping of elements according to pivot’s position.

COMPLEXITY:

Since we know that quick sort is published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heap sort.

Find more in https://www.shoutcoders.com/divide-conquer-algorithm-merge-sort-shout-coders

Algorithm

Step 1 − Choose the highest index value as pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot

Pseudocode

C PROGRAM:

PYTHON PROGRAM:

INPUT-OUTPUT

In this figure, At first 70 is taken as pivot element. After that, {10, 30, 40, 50} are less than 70 so it taken as left array and {80, 90} are greater than 70 so it taken right array. We recursively perform three steps: 1. Bring the pivot to its appropriate position such that left of the pivot is smaller and right is greater. 2. Quick sort the left part. 3. Quick sort the right part. During each pass if pivot value is greater than array value(s) then pivot value is not changed but yes, array values at ith and jth position values are changed. That is all lesser value will stored in first half, then pivot value, then at right half all greater values. After that, pivot value is placed at correct position but both left and right half are not sorted, to sort them, (since quick sort a recursive function), we call the partition function again for left half and taken 50 as pivot. As it is already at its correct position we call the quick sort function again on the left part where 40 taken as pivot element. Similarly, 30 and 10 also become pivot and left array is sorted. After that, Coming to the right part and take 80 as pivot. After that, pivot value 80 is placed in the correct position. Array is sorted fully.

You might like

Saif

About the Author: Saif

Leave a Reply

Your email address will not be published. Required fields are marked *

Close Bitnami banner
Bitnami