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:

- Elements less than the Pivot element
- Pivot element(Central element)
- 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
function partitionFunc(left, right, pivot) leftPointer = left rightPointer = right - 1 while True do while A[++leftPointer] < pivot do //do-nothing end while while rightPointer > 0 && A[--rightPointer] > pivot do //do-nothing end while if leftPointer >= rightPointer break else swap leftPointer,rightPointer end if end while swap leftPointer,right return leftPointer end function |

## C PROGRAM:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<stdio.h> int partition(int sort_list[], int low,int high) { int i=(low-1); int temp,temp2; int pivot=sort_list[high]; for (int j=low;j<high;j++) if (sort_list[j] <=pivot) { i+=1; temp=sort_list[i]; sort_list[i]=sort_list[j]; sort_list[j]=temp; } temp2=sort_list[i+1]; sort_list[i+1]=sort_list[high]; sort_list[high]=temp2; return (i+1); } void quick_sort(int sort_list[],int low,int high) { int pi; if (low< high) { pi=partition(sort_list,low,high); quick_sort(sort_list,low,pi-1); quick_sort(sort_list,pi+1,high); } } int main() { int i, size, lst[25]; printf("Enter size of the list: "); scanf("%d",&size); for(i=0; i<size; i++){ printf("Enter an element: "); scanf("%d",&lst[i]); } quick_sort(lst, 0, size-1); printf("\nOrder of Sorted elements: "); for(i=0; i<size; i++) { printf("%d ",lst[i]); } return 0; } |

PYTHON PROGRAM:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
def partition(sort_list, low, high): i=(low -1) pivot = sort_list[high] for j in range(low, high): if sort_list[j] <= pivot: i+=1 sort_list[i], sort_list[j]= sort_list[j],sort_list[i] sort_list[i+1],sort_list[high]=sort_list[high], sort_list[i+1] return (i+1) def quick_sort(sort_list, low, high): if low < high: pi=partition(sort_list, low, high) quick_sort(sort_list, low, pi-1) quick_sort(sort_list, pi+1, high) lst=[] size=int(input("Enter size of the list: ")) for i in range(size): elements=int(input("Enter an element: ")) lst.append(elements) low=0 high=len(lst)-1 quick_sort(lst, low, high) print(lst) |

## INPUT-OUTPUT

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Enter size of the list: 10 Enter an element: 9 Enter an element: 7 Enter an element: 8 Enter an element: 6 Enter an element: 4 Enter an element: 5 Enter an element: 3 Enter an element: 1 Enter an element: 2 Enter an element: 0 Order of Sorted elements: 0 1 2 3 4 5 6 7 8 9 |

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.