Quicksort
----------
Developed by Hardeep Singh.
Copyright: Hardeep Singh, 2000-2008.
EMail : seeingwithc@hotmail.com
Website : seeingwithc.org
All rights reserved.
The code may not be used commercially without permission.
The code does not come with any warranties, explicit or implied.
The code cannot be distributed without this header.
Various algorithms exist for the sorting of a given list of numbers/strings. Some of the algorithms are
quite simple such as bubble sort, while others are more complex. Each algorithm has its own pros and
cons, and no single algorithm can be nominated as the best. Quicksort is one of the well known sorting
algorithms and is the subject of this writeup.
Problem: We are given a set of numbers that must be arranged in non-decreasing order. We need to use
Quicksort for the solution.
Note: In the text below, lg(n) means log of n to base 2.
Solution #1: Basic Quicksort, recursive.
---------------------------
Quicksort was developed by C.A.R. Hoare and is a widely used sorting technique, based on divide and
conquer. It is an O(n*n) algorithm in the worst case, which is as bad as insertion and selection sorts.
However, its popularity derives from the fact that it has an excellent average case behaviour of
O(n*log(n)). In practice, Quicksort almost always achieves this behaviour.
Quicksort first selects an element that is to be used as split-point from the list of given numbers. 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.
Consider the list: 4 3 1 7 5 9 6 2 8
Now, assume the first element of the list, 4 as the split-point. Then, after splitting the list will be
arranged as:
3 1 2 4 7 5 9 6 8
Or in some other order, say: 2 3 1 4 ...
That is, the exact order is immaterial. What is important is that the order should be:
1. Elements less than split-point element.
2. Split-point element.
3. Elements greater than split-point element.
After this, the list is divided into lists, one containing the elements less than the split-point
element and the other containing the elements more than the split-point element. These two lists are
again individually sorted using Quicksort, that is by again finding a split-point and dividing into two
parts etc. In the program given below, we will let recursion sort the smaller lists.
In the example, the two sub-lists, are:
2 3 1 and 7 5 9 6 8.
Let us consider another example, this time in more detail.
[Look at http://www.seeingwithc.org/solu1t2_1.jpg]
The list to be sorted is shown at the top. The situation after each of the split operations is also
shown, and for the first split - all the comparison-exchanges are shown in more detail. The number with
a bold square around it is the split point and the part of the list shown in pink is the part that’s
being worked upon in that split operation.
In the original list 53 is chosen as the split point. One by one each number is compared to the split
point. If its greater, the list is left as is. If not, the splitpoint is moved one step to the right and
the number in consideration exchanged with the splitpoint.
At the end of the split operation, the splitpoint element is brought into the middle.
Please make sure at this point you understand how the splitting is happening, based on the drawing
above.
Now let us see the program:
#include
#define MAXELT 50
typedef int key;
typedef int index;
key list[MAXELT];
void main()
{
int i=-1,j,n;
char t[10];
void quicksort(index,index);
do { //read the list of numbers
if (i!=-1)
list[i++]=n;
else
i++;
printf("\nEnter the numbers ");
fflush(stdin);
scanf("%[^\n]",t);
if (sscanf(t,"%d",&n)<1)
break;
} while (1);
quicksort(0,i-1); //sort
printf("The list obtained is "); //print
for (j=0;j*
#define MAXELT 100
#define INFINITY 32760 //numbers in list should not exceed
//this. change the value to suit your
//needs
#define SMALLSIZE 10 //not less than 3
#define STACKSIZE 100 //should be ceiling(lg(MAXSIZE)+1)
int list[MAXELT+1]; //one extra, to hold INFINITY
struct { //stack element.
int a,b;
} stack[STACKSIZE];
int top=-1; //initialise stack
void main() //overhead!
{
int i=-1,j,n;
char t[10];
void quicksort(int);
do {
if (i!=-1)
list[i++]=n;
else
i++;
printf("\nEnter the numbers ");
fflush(stdin);
scanf("%[^\n]",t);
if (sscanf(t,"%d",&n)<1)
break;
} while (1);
quicksort(i-1);
printf("The list obtained is ");
for (j=0;j**x);
do {
i++; //find i
} while (list[i]j)&&(c>first)) {
list[c]=list[c-1];
c--;
}
list[c]=j;
}
}
void quicksort(int n)
{
int first,last,splitpoint;
push(0,n);
while (top!=-1) {
pop(&first,&last);
for (;;) {
if (last-first>SMALLSIZE) {
//find the larger sub-list
split(first,last,&splitpoint);
//push the smaller list
if (last-splitpoint*