quick sort

[aarklon]

Hi folks,

this is the program implementing quicksort

#include<stdio.h>
#include<stdlib.h>
#define swap(a,b){int t; t=a;a=b;b=t;}

int partition(int[],int,int);
void quicksort(int[],int,int);

int main(void)
{
int a[5],i;

for(i=0;i<5;a = (rand()%100)+1,i++);

puts("unsorted array:: ");
for(i=0;i<5;printf("\t%d",a),i++);

quicksort(a,0,5);
puts("sorted array:: ");
for(i=0;i<5;printf("\t%d",a),i++);

return(EXIT_SUCCESS);
}

void quicksort(int a[5],int p,int q)
{
int j;


if(p < q)
{
j = partition(a,p,q+1);
quicksort(a,p,j-1);
//quicksort(a,j+1,q);

}
return;
}

int partition(int a[5],int m,int p)
{
int v = a[m], i = m, j = p;
do
{
do{ i += 1;}while(a <= v && i <= p );

do{j -= 1;}while(a[j] >= v && j >= m);

if(i < j) swap(a,a[j]);

}while(i <= j && i <= p);
a[m] = a[j]; a[j] = v;
return j;
}

my questions are as follows

1)
this program works well on some compilers(djgpp,bloodshed devc++ 4.0)
it is not working on turboc++ version 3.0, i am getting junk values
how to rectify this???

2) is the commented statement in the quicksort function(
quicksort(a,j+1,q); ) redundant


the partitioning is based on the following algorithm

algorithm partition(a,m,p)
/* within a[m],a[m+1].....a[p-1] the elements are re arranged in such
a manner that if initially t = a[m],then after completion a[q]=t for

some q between m and p-1,a[k] <= t for m <= k < q,and a[k] >= t
for q < k < p,q is returned,set a[p] = infinity
*/
{
v = a[m];i=m,j=p;
repeat
{
repeat
i = i+1;
until(a >= v);

repeat
j = j-1;
until(a[j] <= v);

if(i < j) swap(a,a[j])

}until(i >= j);

a[m] = a[j];a[j]=v;
return j;
}

 

[Michael Mair]

Hi folks,

this is the program implementing quicksort

#include<stdio.h>
#include<stdlib.h>

#define swap(a,b){int t; t=a;a=b;b=t;}

If you do not need this very often, consider not using this
macro. It is not exactly generic and does not even give much
clarity.

int partition(int[],int,int);
void quicksort(int[],int,int);

Note that the compiler may be able to help you better if you
give the parameter names in the prototypes.
The above is the same as
int partition(int *,int,int);
void quicksort(int *,int,int);
which has the advantage of making it clear that you work with
pointers.

int main(void)
{
int a[5],i;

for(i=0;i<5;a = (rand()%100)+1,i++);

5 is a magic number here, consider using a symbolic constant
(via #define ARRAY_SIZE 5 or similar) instead.
The above is the same as
for(i=0;i<5;i++)
a = (rand()%100)+1;
which certainly is easier to grasp at one glance.

puts("unsorted array:: ");
for(i=0;i<5;printf("\t%d",a),i++);

quicksort(a,0,5);

This seems to imply that quicksort sorts a from 0 to 5-1.

puts("sorted array:: ");
for(i=0;i<5;printf("\t%d",a),i++);

return(EXIT_SUCCESS);

I would have written a printIntArray(int *array, size_t size)
and a populateIntArray(int *array, size_t size) function such
that main() only obtains the input, calls populateIntArray(),
printIntArray(), quicksort() (yes, I'd have called it something
with Int), and printIntArray() and returns finally.

}

void quicksort(int a[5],int p,int q)

The 5 has no meaning whatsoever, so just leave it out.

{
int j;


if(p < q)
{
j = partition(a,p,q+1);

The above call seems to have implied that "q" is an exclusive
upper array index -- seeing "q+1" passed to partition() does not
exactly fill me with confidence.

quicksort(a,p,j-1);
//quicksort(a,j+1,q);

Why do you not want to sort the upper half of the respective
array? Read up on quicksort, especially the "hard split, easy
join" part.

}
return;
}

int partition(int a[5],int m,int p)

Same as above.

{
int v = a[m], i = m, j = p;
do
{
do{ i += 1;}while(a <= v && i <= p );

do{j -= 1;}while(a[j] >= v && j >= m);

if(i < j) swap(a,a[j]);

}while(i <= j && i <= p);

Oh, it gets just better: In this case, p is potentially
an inclusive upper bound which in principle could make
access to a[6] possible while even a[5] is beyond the
array bounds.

What happens if you pass in m==0, p==0 or m==upper, p==upper?
You access a[-1] or a[upper+1] respectively -- this must not
happen.

a[m] = a[j]; a[j] = v;
return j;
}

my questions are as follows

1)
this program works well on some compilers(djgpp,bloodshed devc++ 4.0)
it is not working on turboc++ version 3.0, i am getting junk values
how to rectify this???

Write a working algorithm.

You do not seed rand() with a random value via srand(), so you get
the same values all the time. Usually one seeds with "time(NULL)".

Take pen and paper and work through your algorithm for array sizes
1, 2, ..., 7, 8 and 16 for values in ascending order, values in
descending order, all the same values, one mixed example with an
ascending series on the even and a descending series on the odd
elements with two elements of equal value.

2) is the commented statement in the quicksort function(
quicksort(a,j+1,q); ) redundant

No. You effectively sort only one or two numbers correctly, the
rest is only grouped accordingly.

Example: 4,5,6,7,8,3,2,1 will be partitioned how if your
partitioning is implemented in one correct manner?
{1,2,3}{4}{8,7,6,5} and {}{1}{3,2}{4}{8,7,6,5} by a second
step -- this will be the sorted order.


Cheers
Michael