Page 1 of 1
quicksort built in
Posted: Mon May 26, 2003 4:48 pm
by titid_gede
how to build sort_function using qsort (buld in) when element array is a structure?
for exam :
typedef struct {
int a, key;
} tdata;
tdata data[1000];
how to sort data, according to elemen key?
Posted: Tue May 27, 2003 7:47 am
by Dominik Michniewski
In such case you must write your own compare routine and pass it as parameter to qsort() function. i.e.
int Compare(const void *a,const void *b)
{
tdata *A = (tdata *)a,*B=(tdata*)b;
return A->a - B->a;
}
and that's all
Best regards
DM
Posted: Mon Jun 09, 2003 3:41 pm
by ec3_limz
Compare function.
[cpp]int cmp(const void *va, const void *vb) {
tdata *a = (tdata*)va;
tdata *b = (tdata*)vb;
return a->key - b->key;
}[/cpp]
Calling the quicksort function.
[cpp]qsort(data, 1000, sizeof(data), cmp);[/cpp]
Quite easy. The skill of using the function comes with experience. Good luck.
Posted: Fri Jun 03, 2005 12:08 pm
by jakabjr
using a->key - b->key is dangerous because of overflow!
if u r not sure it will fit (in the example into int), u shuold use ifs with
<,> or typecast one of them to a larger type (in the example long will do).
Posted: Fri Jun 03, 2005 3:30 pm
by misof
jakabjr wrote:using a->key - b->key is dangerous because of overflow!
if u r not sure it will fit (in the example into int), u shuold use ifs with
<,> or typecast one of them to a larger type (in the example long will do).
long won't do here
The UVa judge uses a 32-bit gcc compiler, here both int and long are 32-bit signed.
Re: quicksort built in
Posted: Mon Jun 13, 2005 9:35 pm
by Alberto
Hi titid_gede.
in the book "PROGRAMMING CHALLENGES" of "Steven S. Skiena And Miguel A. Revilla"
exist an example in page 86 of how using the qsort.
And in your example:
// declare directly with the structure "tdata *" and not with "const void *"
int Compare(tdata *A, tdata*B)
{
if(A->key == B->key)
return A->a-B->a;
return B->key-A->key;
}
in this case the sort is decreasing to "key" and increasing of "a" with the priority in the key
see the problem 10008.
Re: quicksort built in
Posted: Tue Jun 14, 2005 6:03 am
by sumankar
Do you have somewhere something like
I'll assume not, and then
Alberto wrote:
// declare directly with the structure "tdata *" and not with "const void *"
strictly speaking & within the confines of standard C that is wrong.The signature of qsort is :
Code: Select all
void qsort (void *array, size_t count, size_t size, int (*cmp_fn)(const void *, const void *))
which says we pass a void pointer (which the function considers as the start of the array to be sorted), followed by the number of elements, the size of each element in bytes, and a function pointer (i.e. name of a function in most cases) that can compare two members of the array.
So the question is why void * as the argument: because void *(and also char *) are considered to be generic pointers, there is some black magic that goes on so you can automatically convert from typeA * to void * and back, _without_ problem.So you can actually pass in anything you wish and you
dont have to cast them.
Posted: Sat Mar 17, 2007 7:07 pm
by algoJo
Can anybody show what's wrong with this code:
Code: Select all
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct{
int a,key;
}tdata;
tdata data[10];
int cmp(const void *va,const void *vb){
tdata *a=(tdata*)va;
tdata *b=(tdata*)vb;
return a->key-b->key;
}
void fill(void){
int i;
for(i=0;i<10;i++)
{
data[i].key=random(100)+23;
data[i].a=i+2;
}
}
void print(void){
int i;
for(i=0;i<10;i++)
printf("%d %d\n",data[i].key,data[i].a);
}
void main(){
clrscr();
fill();
printf("Before:\n");
print();
qsort(data,10,sizeof(data),cmp);
printf("After:\n");
print();
getch();
}
after qsort all the members of data become 0....
Posted: Sun Mar 18, 2007 12:02 am
by misof
The third argumet of qsort is supposed to be the size of a single element, not of the entire array.
In this case, sizeof(data[0]), or equivalently sizeof(tdata);