quicksort built in

Write here if you have problems with your C source code

Moderator: Board moderators

Post Reply
titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

quicksort built in

Post by titid_gede » Mon May 26, 2003 4:48 pm

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?
Kalo mau kaya, buat apa sekolah?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue May 27, 2003 7:47 am

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

Post by ec3_limz » Mon Jun 09, 2003 3:41 pm

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
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by jakabjr » Fri Jun 03, 2005 12:08 pm

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).
Understanding a problem in a natural way will lead to a natural solution

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Fri Jun 03, 2005 3:30 pm

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.

Alberto
New poster
Posts: 4
Joined: Fri May 20, 2005 5:15 pm
Location: La Paz - Bolivia
Contact:

Re: quicksort built in

Post by Alberto » Mon Jun 13, 2005 9:35 pm

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
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Re: quicksort built in

Post by sumankar » Tue Jun 14, 2005 6:03 am

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.

User avatar
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

Post by algoJo » Sat Mar 17, 2007 7:07 pm

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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Mar 18, 2007 12:02 am

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

Post Reply

Return to “C”