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

Code: Select all

typedef const void *tdata;
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);