11.6 – Quick sort using recursion

by subbu on December 11, 2013

Quick sort:

It is the sorting technique developed by C.A.R Hoare, having very good average among all the sorting techniques.

Quick sort algorithm first selects a value that is to be used as split-point (pivot element) from the list of given numbers. Elements are arranged so that, all the numbers smaller than the split-point are brought to one side of the list and the rest on the other. This operation is called splitting.

After this, the list is divided into sub lists, one sub list containing the elements less than the pivot element and the other containing the elements more than the pivot element. These two lists are again individually sorted using Quick sort algorithm that is by again finding a split-point and dividing into two parts. The process is recursively done until all the elements are arranged in order. So it is called divide and conquer algorithm.

Now we will see how a list can be split and place pivot element at its place, the place of pivot element is a split point for next sub arrays.

Quick sort

We select the first element as pivot element and place it, at its position using an algorithm

p=a[start];  /* Here start is starting index */

We will find the biggest element than the pivot element from first using “i” and smallest element from the last using “j” and interchange them

Quick sort pass 1

i=start;
j=end;

while(a[i]<=p) /* continues until get biggest element than pivot element*/
  i++;

while(a[j]>=p) /* continues until get biggest element than pivot element*/
  j++;

if(i<j)
  temp=a[i],a[i]=a[j],a[j]=temp;  /* inter changing a[i] and a[j] */

We follow the same procedure as long as i<j

Quick sort pass 2

We follow the same procedure as long as i<j

Quick sort pass 3

As i<j is false, the current process is stopped and a[start] and a[j] are interchanged.

Now the pivot element is at its position “j”, which is the split position for next sub arrays because all elements to its left are smaller and to its right are greater.

Quick sort pass 4

a[start]=a[j];
a[j]=p;
return j;  /* returning splitting position */

Quick sort – Splitting position:

int split(int start,int end)
{
 int p=a[start];
 int i=start,j=end,temp;
 while(i<j)
 {
  while(a[i]<=p)
    i++;
  while(a[j]>p)
    j--;
  if(i<j)
    temp=a[i],a[i]=a[j],a[j]=temp;
}
 a[start]=a[j];
 a[j]=p;
 return j;
}

Now this procedure accepts starting, ending index of a sub array and returns split point by arranging the elements so that, all the elements left to split point are smaller than pivot element and right to split point are greater than pivot element

We continue the same process recursively with other sub arrays. It can be done using a recursive procedure

void qsort(int start,int end)
{
 int s;
 if(start>=end)
   return;
 s=split(start,end);
 qsort(start,s-1);         /* takes left sub array to split point */
 qsort(s+1,end);         /* takes right sub array to split point */
}

Quick sort step by step

Quick sort implementing in C:

#include<stdio.h>
int a[50];
void qsort(int,int);
int split(int,int);
int main()
{
 int n,i;
 printf("How many elements?");
 scanf("%d",&n);
 printf("Enter %d elements:\n",n);
 for(i=0;i<n;i++)
  scanf("%d",&a[i]);
 qsort(0,n-1);
 printf("The resultant array:\n");
 for(i=0;i<n;i++)
   printf("%5d",a[i]);
 return 0;
}
void qsort(int start,int end)
{
 int s;
 if(start>=end)
  return;
 s=split(start,end);
 qsort(start,s-1);
 qsort(s+1,end);
}
int split(int start,int end)
{
 int p=a[start];
 int i=start,j=end,temp;
 while(i<j)
 {
   while(a[i]<=p)
     i++;
   while(a[j]>p)
     j--;
   if(i<j)
     temp=a[i],a[i]=a[j],a[j]=temp;
 }
 a[start]=a[j];
 a[j]=p;
 return j;
}

Execution:
How many elements?9
Enter 9 elements:
40 90 60 5 13 10 20 45 50
The resultant array:
5   10   13   20   40   45   50   60   90

Efficiency of quick sort:

Both selection sort and insertion sort takes n2 steps to sort n elements. Say for example takes 100 (102) steps to sort 10 elements. Where as quick sort takes log2n steps to sort n elements that is, takes 3 steps to sort 10 elements. Quick sort is considered as the most efficient method of sorting.

Previous post:

Next post: