Quick Sort

INCREASING ORDER:

 There are Two functions in this

i)The quicksort function which is a recursive function

2)This is for partitioning and to execute quick sort

void quicksort(int arr[],int first,int last)

{

     int pivot;

    if(first<last)

   {

         pivot=partition(arr,first,last);

         quicksort(arr,first,pivot-1);

         quicksort(arr,pivot+1,last);

   }

}

int partition(int arr[],int first,int last)

{

     int pivot,i,j;

     pivot=arr[last];

     i=first-1;

    while(j=first;j<last;j++)

     {

            if(arr[j]<pivot)

            {

                i++;

                swap(&arr[j],arr[i]);

          }

    }

 /*by now i,j,pivot will be in a position

    the numbers up till i are value which are less than pivot

   and numbers after i till j are values greater than pivot..So

   swap the element i+1 and pivot so that pivot will be in a exact position where it should be if it is sorted*/

        

    

 swap(&arr[i+1],&arr[last]);

 return i+1;

}

The things need to remember here are,every time partition function executed j will be in the beginning of array,i will be one less than beginning.As we need increasing order output while moving in loop,whatever values greater than pivot are left and when less than that i is incremented and swaped with tha value of j.so by this way at end of loop,i may be somewhere in middle of loop and whatever values up till

i are less than pivot.

Time Complexity:

      Best Case and Average case:

                         Assuming that after one iteration pivot is exactly at middle,so the next two quick sort function divide left and right part of pivot into two halves then

  T(n) be time taken for n size

void quicksort(int arr[],int first,int last)------------> T(n)

{

     int pivot;

    if(first<last)

   {

         pivot=partition(arr,first,last);---------------->O(n)//one loop

         quicksort(arr,first,pivot-1);---------------->T(n/2)

         quicksort(arr,pivot+1,last);---------------->T(n/2)

   }

}

in best case pivot is middle and they are divided into halves..Even in average case one may be T(n/4) and T(3n/4) any way we compute it as

 T(n)=2T(n/2)+O(n)

using masters theorem we can find that T(n)=O(nlogn)

Worst case:

  

  i)array is in increasing order

  ii)array is in decreasing order

iii)array has all numbers equal

Then take an example and check you can found out that after one iteration,pivot will be exactly in that location..The problem here is Since it is in increasing order pivot is last element and even after one iteration..Now the array is divided in such a way that it is shown in below

void quicksort(int arr[],int first,int last)------------> T(n)

{

     int pivot;

    if(first<last)

   {

         pivot=partition(arr,first,last);---------------->O(n)//one loop

         quicksort(arr,first,pivot-1);---------------->T(0)

         quicksort(arr,pivot+1,last);---------------->T(n-1)

   }

}

depending on input either of recursive calls can be T(0) and T(n-1)

T(n)=T(n-1)+n

      =T(n-2)+n-1+n

      :

      :

      :

      =O(n^2)

Even if the array is divided into 1:9 then also time is O(nlogn) in the video

and in worst case it is O(n^2) because it is divided as 0:10

Space complexity can be O(logn) because it uses Stack while recursive calls