Entry

Quick Sort Algorithm and Program

May 23rd, 2004 09:32
Sudipto Kumar Mukherjee,

Quick sort is one of the very effective sorting technique.
Quick sort is explained differently by different authors. But the
basic concept remains the same!
Here is how the concept is:
Suppose you are having different children standing in a line.
They also do not maintain any height order. That is, the shortest
child may even stand in the middle. Normally you remember that
you would have to stand in assending order of height in your 
school PT. You have to arrange them in assending order. If
you follow the method of quick sort, you should proceed as follows...
Take one child out, normally the first child. Let us call that
child as pivot. Now call one by one other children. When each of them 
come, compare him/her with the pivot. If the child is shorter than
or equal to the pivot, make the child (not pivot) stand in your left 
hand side of the pivot. But if the child is taller than the pivot, make 
him/her stand on the right hand side. 
So, when you are finished calling all the childern, you have all the
shorter children compared with the pivot in the left hand side & all
the taller one in your right.
If stick represent a child then after this process finishes I will
end up like this:
                      |
                      |       |
                pivot |   |   |
                  |   |   |   |
                  |   |   |   |
     |        |   |   |   |   |
|    |        |   |   |   |   |
|    |    |   |   |   |   |   |
|    |    |   |   |   |   |   |    
<--LEFT SIDE-->       <--RIGHT SIDE-->
Do you agree that the pivot has found its correct position?
That is, when the children will be standing in their perfect
assending order, pivot will not be shifted anywhere in the line.
After all all the shorter are ahead of pivot & all the taller
are behind.
Now think if you apply this same mechanism for the children standing
on the left and right seperately then you will end up getting more and 
more child getting his/her perfect position. 
With this much understanding, I present you a C program:
Here I have taken seperate place for storage of left & right
members. Then when the pivot gets its place, I simply copied
the contents of left storage (array) to the list, followed by 
the pivot element, then followed by coping of the right members.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
void quicksort(int* list,int min, int max)
{
 int *small;
 int *large;
 int i,s=0,l=0,k;
 int pivot,pivotpos;
 if(max <= min)
 return;
 pivot = list[min];
 small=malloc(sizeof(int)*(max-min+1));
 large=malloc(sizeof(int)*(max-min+1));
 for(i = min + 1; i <= max; i++)
 {
  if(list[i] <  pivot)
   small[s++] = list[i];
  else
   large[l++] = list[i];
 }
 k=min;
 for(i = 0; i < s; i++)
  list[k++] = small[i];
 list[k++] = pivot;
 pivotpos = k - 1;
 for(i = 0; i < l; i++)
  list[k++] = large[i];
 free(small);
 free(large);
 quicksort(list,min,pivotpos-1);
 quicksort(list,pivotpos+1,max);
}
void main()
{
 int list[]={3,2,1,5,10,4,6,7,5,9,8};
 int i;
 clrscr();
 for(i=0;i<11;i++)
 {
  printf("%d ",list[i]);
 }
 printf("\nApplying quicksort...\n");
 quicksort(list,0,10);
 for(i=0;i<11;i++)
 {
  printf("%d ",list[i]);
 }
 getch();
}