# Divide and conquer Applications:

## Quick sort:

- Quick sort is based on
**DIVIDE & CONQUER**approach. - In quick sort, we divide the array of items to be sorted into two partitions and then call the quick sort procedure recursively to sort the two partitions.
- To partition the data elements, a pivot element is to be selected such that all the items in the lower part are less than the pivot and all those in the upper part greater than it.
- The selection of pivot element is somewhat arbitrary; however, the first element is a convenient one.

**Example: **Elements are 5 3 2 6 4 1 3 7 and Pivot – 5

(a{j] with a[i]) -> At this position pivot is placed in its sorted position and two sub lists are generated. Apply **Quick sort** procedure recursively to each sub list.

Algorithm for Quick Sort is given below:

## Quick Sort Time Complexity:

- Suppose each partition operation divides the array almost exactly in half then the depth of the recursion in
**log**_{2}n - At each level of the recursion, all the partitions at that level do work that is linear in
**n**i.e.,**O(log**_{2}n) * O(n) = O(n log_{2}n) - Hence in the average case,
**quick sort**has time complexity**O(n log**_{2}n) - In the worst case, partitioning always divides the size n array into these three parts:
- A length one part, containing the pivot itself
- A length zero part, and
- A length n-1 part, containing everything else

- Recurring on the length n-1 part requires (worst case) recurring to depth n-1
- But the partitioning work done at each level is still n i.e., O(n) * O(n) = O(n
^{2}) - So worst case time complexity for
**Quick sort**is**O(n**^{2})