The quicksort is an example of a divide and conquer algorithm in that it divides the sorting problem into smaller problems by dividing the list of items to be sorted into smaller subsets. The pivot is the mechanism that is used to segment the list. Describe how the quicksort works including a discussion of the pivot, how it is selected, and why the pivot is important to the quicksort.

Quick Sort is a Divide and Conquer algorithm which picks an element as pivot and partitions the given array around the picked pivot.  we can pick pivot in various ways, Always picking first element of array as pivot, Always picking last element of array as pivot Picking a random element of array as pivot, Pick median of array as pivot.

partition():

The Main process in quick Sort is partition(). Output of partitions is location i , which means

• all element to the left of i (0 1 2 ... (i-1) are less than a[i] and
• all element to the right of i (i+1, i+2 , ...... n ) are greater than a[i].

This take O(n) time every time when we call.

Problem in Quick Sort Algorithm: we know that Quick Sort is a Divide and Conquer algorithm but partition (divide) in Quick sort are not always good in quick sort.

• when partition are equal then it shows Best time complexity of quick sort O(n log₂n)

T(n) = T(n/2) + T(n/2 + O(n) // one side n/2 element and another side n/2 elements

• when partition are NOT equal then it shows Worst time complexity of quick sort O(n²)

T(n) = T(1) + T(n-1) + O(n) // one side 1 element and another side (n-1) elements

Importance of Pivot element in Quick sort:

The time behavior(time complexity of quick sort algorithm is depends on selection of pivot value .

consider various inputs

• Input: 1 2 3 4 5 6 7 8 9 10 if pivot p = a[i] = 1
• If we select pivot element as starting element and input is in increasing order then it divide the array into un qual parts which show worst case time complexity of quick sort.
• T(n) = T(1) + T(n-1) + O(n)
• 1 2 3 4 5 6 7 8 9 10 one side 1 element( means no element to process) and another side (n-1) elements

• Input: 1 2 3 4 5 6 7 8 9 10
•  pivot p = a[j] = 10
• If we select pivot element as ending element and input is in increasing order then it divide the array into un qual parts which show worst case time complexity of quick sort.
• T(n) = T(n-1) + T(1) + O(n)
• 1 2 3 4 5 6 7 8 9 10 one side (n-1) element( means no element to process) and another side 1 elements
• Input: 1 2 3 4 5 6 7 8 9 10
•  pivot p = mid element = 5
• If we select pivot element as middle element and input is in increasing order then it divide the array into equal parts which show best time complexity of quick sort.
• T(n) = T(n/2) + T(n/2) + O(n) // one side n/2 element and another side n/2 elements
• 1 2 3 4 5 6 7 8 9 10 one side almost half element and another almost side half elements

•  

   

• if input is some random like Input: 6 5 8 9 12 11 25 4 2
• pivot p = a[i] = 6
• If we select pivot element as starting element and input is in random order then if it divide the array into equal parts(or some almost equal parts / some fraction )
• T(n) = T(1) + T(n-1) + O(n)
• (all elements less than 6 ) 6 (all elements greater than 6 )
• 2 4 5 6 8 9 12 11 25 // here we are getting best case of quick sort algorithm

• so selection of pivot in quick sort decide partition (whether equal partition ot unequal partition )which which affect running time of quick sort algorithm.

• Quick sort Algorithm:

   

  Quicksort(A,p,q) // A is array p is pointer to start and q is a pointer to end

  {

  if (p==q)

  { return A;}

  else

  {

  m =partition(A,p,q);   // this will call partition algorithm // O(n)

  Quicksort(A,p,m-1);

  Quicksort(A,m+1,q);

•  

  }

  return A;

  }

   

  ---------------------------

  Partition(A,p,q) {

  x=A[p]; // picking first element of array as pivot

  i=p;

  for(j=p+1; j q ; j++)

  {

  if (A[j] x)

  {

  i=i+1;

  interchange(A[i],A[j]);

  }

  interchange(A[p],A[i]);

  returen i ;

  }

  }