Quick sort is a faster way to sort a given array by recursion
The algorithm goes like this:
it first takes some index element and seperates all elements lesser than this with larger numbers then places this element in right place and does the same thing with all other
#define maxsize 6
int A[maxsize];
void quicksort(int a, int b)
{
int rtidx=0,ltidx=0,k=a,l=0,pivot;
int leftarr[maxsize],rtarr[maxsize];
pivot=A[a];
if(a==b)return;
while(k<b)
{
++k;
if(A[k]<A[a])
{
leftarr[ltidx]=A[k];
ltidx++;
}
else
{
rtarr[rtidx]=A[k];
rtidx++;
}
}
k=a;
for(l=0;l<ltidx;++l)A[k++]=leftarr[l];
A[k++]=pivot;
for(l=0;l<rtidx;++l)A[k++]=rtarr[l];
if(ltidx>0)quicksort(a,a+ltidx-1);
if(rtidx>0)quicksort(b-rtidx+1,b);
}
void printarr(int a)
{
int i;
for(i=0;i<a;i++)
{
printf("%d",A[i]);
printf("\n");
}
}
main()
{
int i,s;
printf("enter the number of numbers to be entered \n");
scanf("%d",&s);
for(i=0;i<s;i++)
{
printf("enter the number \n" );
scanf("%d",&A[i]);
}
printf("array before sorting ");
printarr(s);
quicksort(0,s-1);
printf("array after sorting");
printarr(s);
}
I used your code replacing the array of ints with an array of floats and erased maxsize so that i can give the size i want. The whole thing runs ok till the 210000 array size. After i get segmentation faults and bus errors. sizeof int and sizeof float are both 4. Can anybody help me with that?
Your sorting is used for only integer,i need a quick sort which is generic to all basic types such as int, float, char and struct types
Your sorting is used for only integer,i need a quick sort which is generic to all basic types such as int, float, char and struct types
What you are looking for is qsort(), and it's part of the C standard library. The good part of it is that it handles all data types. The bad part is that it is not easy to set up the compare function correctly to handle those void pointers it requires.
This code is not the best example of Quicksort - rather poor actually. It constantly sets the pivot point RIGHT where the pivot point is likely to be a bad value.
Quicksort is VERY sensitive to a bad pivot point - it will degrade to something approaching a bubble sort, under worst case selections, and may crash entirely if the sub-arrays being generated by Quicksort, are not taken smaller one first, at all levels of recursion.
compare function in c standard library qsort() is not difficult, but the point is we have to handle the void pointer's carefully.I tried my level best to write a generic version of qsort() as c standard library, but i cant .
//this is my compare() for integer, i think here there is no problem with void*
int compare(const void *arg1, const void *arg2)
{
return (*(int*)arg1) > (*(int*)arg2);
}
if you can means pls write it...
You are quite the politician! In one paragraph, you say the compare function is not difficult to write for qsort().
On the very next paragraph, you state that you're unable to write the compare function for qsort(). ;)
I don't use qsort(), because I prefer other versions of quicksort. This is what I use for integers, when I use qsort():
//for integers:
int compare_int(const void *a, const void *b) {
return(*(int*)a - *(int*)b);
}I consider this compare function difficult to code up correctly, "on the fly".
(also, my Quicksort versions are quite a bit faster then qsort)
This is the compare function for strings using qsort(), btw:
//for strings
int compare_str( const void *a, const void *b) {
return(strcmp(a,b));
}This is the best Quicksort version I've found and tested for run time. It's simple, clear, unoptimized, but fast:
//Quicksort w/o a separate compare function :)
void quicksort(int A[], int lo, int hi) {
int i, j, pivot, temp;
if(lo == hi) return;
i=lo;
j=hi;
pivot= A[(lo+hi)/2];
/* Split the array into two parts */
do {
while (A[i] < pivot) i++;
while (A[j] > pivot) j--;
if (i<=j) {
temp= A[i];
A[i]= A[j];
A[j]=temp;
i++;
j--;
}
} while (i<=j);
if (lo < j) quicksort(A, lo, j);
if (i < hi) quicksort(A, i, hi);
}To optimize it by about 12%, change the "if(lo==hi) return" statement near the top of the code. Have it call an insertion() sort function, if the number of elements in the array (or sub-array) being considered, is < about 40. The ideal number varies from system to system, so it should be tested.
This version has some nice logic:
*it always takes the smaller sub-array to finish off first, which saves on stack space.
*has a "middle of the bunch" pick for a pivot, so data that is already nearly sorted, will not "bust" it so easily.
*needs no separate compare function - it's built right into it for int's. Simple
to change that area of code, for strings.
*it's a fast design, and it's easy to further optimize
*it's intuitive code. With study, you can see exactly, how Quicksort works.
writing compare() is not a difficult task and also i am not politician, i can write compare() for all types, but i cant able to write the generic version only. thats what i want to tell you
Hey admin,
Excellent post for the quick short program.
of course this blog is doing a very good job of serving useful information. I'm proud to be a part of its Readers community.
for more information of this program visit http://writeaprogramto.blogspot.com/2013/05/program-for-shorting.html
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.