quicksort built in

[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?

[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

[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.

[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).

[misof]

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.

[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.

[sumankar]

Do you have somewhere something like

Code: Select all

typedef const void *tdata;

I'll assume not, and then

// 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.

[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....

[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);