Divide and conquer Applications:

Quick sort:

1. Quick sort is based on DIVIDE & CONQUER approach.
2. 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.
3. 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.
4. 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:

Algorithm Quicksort( l, h)
{
if(l<h) then
{
q:=Partition(l,h);
Quicksort(l,q-1);
Quicksort(q+1,h);
}
}

Algorithm Partition( l, h)
{
i:=l;
j:=h;
p:=a[l];
while(i<j) do
{
while(a[i]<=p and i<h) do
i:=i+1;
while(a[j]>=p and j>l) do
j:j-1;
if(i<j) then
{
temp:=a[i];
a[i]:=a[j];
a[j:]=temp;
}
}
a[j]:=p;
a[l]:=a[j];
return j;
}

Quick Sort Time Complexity:

• Suppose each partition operation divides the array almost exactly in half then the depth of the recursion in log₂n
• At each level of the recursion, all the partitions at that level do work that is linear in n  i.e., O(log₂n) * O(n) = O(n log₂n)
• Hence in the average case, quick sort has time complexity O(n log₂n)
• In the worst case, partitioning always divides the size n array into these three parts:
  1. A length one part, containing the pivot itself
  2. A length zero part, and
  3. 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²)
• So worst case time complexity for Quick sort is O(n²)