question about qsort

[xcgames]

first of all, thx to all experts who help out here


ok I have this array of structs that i used qsort function to sort.

the struct contains a number and a pass #

struct progSorted{
   int num;
   int pass;
};

and I've created an array of structs and loaded every member in the array with a num and pass.

i've used run-to-cursor feature in VS.NET and made sure that data has properly filled in the struct array properly before calling the qsort function.

progSorted[0].number = 0
progSorted[1]number = 2
progSorted[2].number = 1
progSorted[3].number = 3
progSorted[4].number = 4
progSorted[5].number = 5
progSorted[6].number = 6
progSorted[7].number = 7
progSorted[8].number =11       // this number belongs to another pass and so on

then I called qsort function to sort it, and qsort filled with 0s and other numbers unrelated to anything I filled in earlier.

qsort (&progSorted[sortPosition].number, numToSort, sizeof(int), compare);
     //numToSort = 8, sortPosition = 0

everything in the program works as expected up until the program runs that line of code. can somone tell me what i am doing wrong here?

much thanks...

 

[xcgames]

this solves the problem

	qsort (&progSorted[sortPosition].number, numToSort, sizeof(progSorted[sortPosition]), compare);

 

[Lord of Shadows]

For the fun of it, an unoptimized, in place, clrs style implementation of quicksort. For those unfamilar with the quicksort algorithm, you pretty much choose a number, call it a pivot, and put everything less than it on one side, everything greater than it on the other side, and then put the pivot in the middle. This middle position is the pivots final position. You then repeat with the sublists.

void quickSort(int list[], const int left, const int right)
{
	int mid;

	if (left < right)
	{
		mid = partition(list, left, right);
		quickSort(list, left, mid - 1);
		quickSort(list, mid + 1, right);
	}
}

int partition(int list[], const int left, const int right)
{
	int pivot = list[right];
	int i, temp;
	int mid = left;

	for (i = left; i < right; i++)
	{
		// keep everything less than pivot on left
		if (list[i] <= pivot)
		{
			temp = list[i];
			list[i] = list[mid];
			list[mid] = temp;
			mid++;
		}
	}
	// put pivot in middle
	temp = list[right];
	list[right] = list[mid];
	list[mid] = temp;
	return mid;
}

Edit: Upper bound is O(n^2) lower bound is Omega(nlogn).

 

[mikeblas]

this solves the problem

	qsort (&progSorted[sortPosition].number, numToSort, sizeof(progSorted[sortPosition]), compare);

I think you're being lucky; I don't think your first parameter is correct.

 

[movax]

I think you're being lucky; I don't think your first parameter is correct.

Indeed, the struct is named "progSorted", but yet he has stated he has an "array of structs"...dunno, the code is a bit confusing. (To me anyways.)

 

[Lord of Shadows]

I'm not seeing anything wrong assuming this looks like what he is doing:

#include <stdio.h>

int compare(const void *one, const void *two);

struct progSorted
{
	int number;
	int pass;
};

int main(void)
{
	int i, sortPosition = 0;
	struct progSorted progSorted[16];

	progSorted[0].number = 0;
	progSorted[1].number = 2;
	progSorted[2].number = 1;
	progSorted[3].number = 3;
	progSorted[4].number = 4;
	progSorted[5].number = 5;
	progSorted[6].number = 6;
	progSorted[7].number = 7;

	progSorted[8].number = 11;
	progSorted[9].number = 10;
	progSorted[10].number = 9;
	progSorted[11].number = 8;
	progSorted[12].number = 7;
	progSorted[13].number = 6;
	progSorted[14].number = 5;
	progSorted[15].number = 4;

	qsort(&progSorted[sortPosition].number, 8, sizeof(struct progSorted), compare);
	sortPosition += 8;
	qsort(&progSorted[sortPosition].number, 8, sizeof(struct progSorted), compare);


	for(i = 0; i < 16; i++)
		printf("%d\n", progSorted[i].number);

	return 0;
}

int compare(const void *one, const void *two)
{
	if ( *((int *)one) > *((int *)two) )
		return 1;
	else if ( *((int *)one) < *((int *)two) )
		return -1;
	else
		return 0;
}

I dont see why you would name your structure and structure array the same thing, but it compiles. As for the first base pointer parameter to quicksort I see nothing wrong about it.

 

[MonkeyShave]

What about when your coworker comes along (next year) and changes the structure to

struct progSorted
{
	int pass;
	int number;
};

A well-written driver program and comparison function would be stable in the face of this change (work with no alteration). No program or fragment presented here would work with that, indicating a failure to understand the behavior of qsort.

 

[Lord of Shadows]

You're right, I assumed that qsort took a stride parameter from looking at his call. (Which should have been obvious because the size would still have been required.) -- My question: how do you change the default stride for qsort?

I suppose you would just have to write it into your compare function.

 

[MonkeyShave]

The stride (named width in my docs) isn't the problem. Your sample uses that correctly as the third parameter.

The OP reads like a homework question, so I won't spell it out explicitly, but the problem is one of type-safety. Both qsort() and its compare() function use void * which eliminates any chance of having the compiler check types. As such, the programmer needs to push types back in, but, lacking that, you'll most likely get wrong output. If you're lucky, you'll get an access violation or segfault on the modified version, but it's not likely (in an unmanaged environment).

 

[Lord of Shadows]

I understand my folly ;o)