C Program for Quick Sort

Problem: Write a C program for quick sort. C program to accept and sort an array in ascending as well as descending order using quick sort algorithm.
Procedure:

We consider one element at a time and place it in its correct position. This element is called as pivot.

This pivot is placed such that all elements to the left of the pivot are less than the pivot and all elements to the right are greater. This partitions the array into two parts -left partition and right partition. The same method is applied for each of the partition. This process continues till no more partitions can be made

Note: Any element can be chosen as pivot.

We are considering the first element as pivot element. The recursive function is similar to merge sort. However, in quick sort, we do not divide into two equal parts but partition on the basis of the pivot element. The function sorts the elements a[lb] to a[ub] where lb=lower-bound and ub=upper-bound .

void QuickSort(int a[],int lb,int ub)
{
   int j;

   if(lb<ub)
   {
      j=partition(a,lb,ub);
      QuickSort(a,lb,j-1);
      QuickSort(a,j+1,ub);

   }

}

Now we use two variables up and down for moving down and up the array in partition function.

Algorithm For Partitioning:

1. Start
2. down=lb
3. up=ub
4. pivot=A[lb]
5. while(A[down]<=pivot && down<ub)
   down++
6. while(A[up]>pivot && up>lb)
   up--
7. if(down<up)
   interchange A[down] and A[up]
   goto step 5
8. Interchange A[up] and A[lb]
9. return up
10. stop.

C Program for quick Sort:

Get This Program: