Quick sort

QUICK SORT
Definition:  Quicksort is based on a divide and conquer  method.
It works recursively, by first selecting a random “PIVOT VALUE” from the array.
Then the partition function works in a way that the elements that are less than pivot value is placed left of pivot value and the elements are greater is placed right of the pivot value, it works recursively until the elements are placed  in sorted order.
Quicksort, sometimes called partition-exchange sort.
Algorithm for Quick Sort:  
a) Algorithm for partition the unsorted array.
                Partition(a,lb,ub)
{
     pivot=a[lb];
    start=lb;          // pivot  is a random value.
     end=ub;  //lb is lower bound of array & ub is upper bound.
    while(start<end)
    {
        while(a[start]<=pivot)
start++;
         while(a[end]>pv)
          end--;
        if(start<end)
        {
            temp=a[start];       // swapping function works.
            a[start]=a[end];
            a[end]=temp;
        }
    }
    temp=a[lb];
    a[lb]=a[end];
    a[end]=temp;   // swapping the pivot value with end value.
    return end;      }
b) Algorithm for Quick sort:
quicksort(a,lb,ub)
{
    if(lb<ub)
    {                              // loc is location return by a partition function.
        loc=partition(a,lb,ub);    // function is calling for partition.
        quicksort(a,lb,loc-1);
        quicksort(a,loc+1,ub);
    }
}
Code for Quick Sort:
#include<stdio.h>
int partition(int *,int ,int);
void quicksort(int *,int,int);
int main()
{
    int a[20],i,n;
    printf("How many number do u want to execute. ");
    scanf("%d",&n);
    printf("Enter the element one by one. ");
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    quicksort(a,0,n-1); // calling the quick sort.

   printf("Order of Sorted elements: ");
   for(i=0;i<n;i++)
      printf(" %d",a[i]);
    return 0;
}
int partition(int a[],int lb,int ub)
{
    int temp;
    int pv=a[lb];
    int start=lb;          // pv is a random pivot value, in our case 1st element is pivot element.
    int end=ub;
    while(start<end)
    {
        while(a[start]<=pv)
        {
            start++;
        }
        while(a[end]>pv)
        {
            end--;
        }
        if(start<end)
        {
            temp=a[start];       // swapping function works.
            a[start]=a[end];
            a[end]=temp;
        }
    }
    temp=a[lb];
    a[lb]=a[end];
    a[end]=temp;
    return end;
}
void quicksort(int a[],int lb,int ub)
{
    int loc;
    if(lb<ub)   // loc is location return by the partition function.
    {
        loc=partition(a,lb,ub);  // function is calling for partition.
        quicksort(a,lb,loc-1);
        quicksort(a,loc+1,ub);
    }
}


Output of the Program:
  

Example of the Quick Sort :

Time Complexity for Quick Sort:
Worst Case  [ Big-O ]: O(n2)
Best Case  [Big-omega]: O(nlog n)
Average Case [Big-theta]: O(nlog n)
Space Complexity: O(nlog n)