sort problem for an exam

I would like an opinion from visitors and senior programmers on the following test question that I'm considering to give to a class of students who are beginning to learn C programming. If I was to ask these students to describe what is going on with this sort program, do think it would be fair to ask them this when they only have an 1 hour and 45 minutes to complete it the 10 question exam. I feel that these students should spend at the most, 30 minutes on this question. Tell me what you think? If you want... try to answer the question. I know how much you guy's like a challenge!

Thank you!

Code:

#include <stdio.h>
#define N 10


void quicksort(int a[], int low, int high);
int split(int a[], int low, int high);

main()
{

	int a[N], i;

	printf("Enter %d numbers to be sorted: ", N);
	for(i = 0; i < N; i++)
		scanf("%d", &a[i]);

	quicksort(a, 0, N - 1);

	printf("In sorted order: ");
	for(i = 0; i < N; i++)
		printf("%d ", a[i]);
	printf(" \n");

   getchar();
   getchar();
	return 0;
}

void quicksort(int a[], int low, int high)
{
	int middle;

   if(low >= high) return;
	middle = split(a, low, high);
	quicksort(a, low, middle - 1);
	quicksort(a, middle + 1, high);
}

int split(int a[], int low, int high)
{
 	int part_element = a[low];

 	for(;;){
   	while(low < high && part_element <= a[high])
   		high--;
   	if(low >= high) break;
   	a[low++] = a[high];

   	while(low < high && a[low] <= part_element)
   		low++;
   	if(low >= high) break;
   	a[high--] = a[low];
	}

 	a[high] = part_element;
 	return high;
}

It really depends on what they know already. If they are already familiar at all with sorting algorithms, then I think they can do it. However if they've never done a sort before then I personally think that this will stump many students.

They have been studying recursions, and now studying pointers. The group is intelligent but I'm still not sure if this question is appropriate because I don't know how they would answer the question. That's why I was hoping to get a few visitors to maybe answer the question and I could do a comparision. Thanks

I would fail you as a teacher for not implicitly defining main to return an int. You're taking the lazy approach, which is never a GoodThing(TM). But looking on the bright side, at least you didn't use void main...

Furthermore, the function 'split' is one of the ugliest pieces of code I have seen in a long time.

Quzah.

Quzah... There are numerous ways to improve this programs performance, including:

1. improving the paritioning algorithm;
2. using a different method to sort small arrays; and
3. making the program nonrecursive.

however, i need these students to understand the basics.
Can you tell me how you would answer my question? Thanks!

I actually started to do this. I copied the code into a text editor, and started commenting it line by line. That's how I'd actually answer your question.

I got to the loop in the function 'split' and quit, because it's damn ugly code, and quite honestly, it's hard to follow.

Quzah.

Can you send your comments? I would really like to see them!
I know that this program looks ugly to an experienced programmer, and I respect your comments but you are an exception.

Originally posted by rjeff1804
Can you send your comments? I would really like to see them!
I know that this program looks ugly to an experienced programmer, and I respect your comments but you are an exception.

So I'm to assume that you are not a student, and that this isn't a homework assignment? Ok. I'll play along. Here are my comments:

Code:

/* standard includes for IO */
/* define a macro, N */

/* prototype two functions */

/* sort of declare main, -2 points ;) */
	/*
		create an array of ints, N elements in size
		and an integer i
	*/

	/*
		Prompt for N numbers. This could be clearer,
		but it is sufficient.
	*/
		/* store the number */
		/*
			You don't check the scanf return, 
			I can break your program here.
		*/

	/*
		Call quicksort, passing it the array, a start
		and an end point.
	*/

	/* Display the sorted array. */

	/* read a few characters, terminate the program */

/* define the quicksort function */
	/* declare an integer */

	/* make sure the low is less than high */
	/* find the "middle" */

	/*
		recursivly call quicksort, passing it new
		starting and end points. In the first one,
		we pass it values before midpoint. In the
		second, we pass it values beyond the mid-
		point.
	*/

/* Define the split function. */
	/* define an int to hold the value in the 'low' position */

	/* loop indifinately */
		/*
			Compare each element in the array to
			the original value, until you find one
			that is less than the starting value,
			moving backwards from the 'high' point.
		*/
		/* if we've not found such a value, break */

		/*
			overwrite the value in the starting
			position with the found value, and
			then increment the low value
		*/

		/*
			Compare each element in the array
			to the original value until we find
			one that is greater, moving foreward
			from the "new low".
		*/

		/* if we have not found such a value, break */

		/*
			overwrite the value in the current
			high position with the found value,
			and then decrement the high value
		*/

	/* overwrite the current high point with the first value */

	/* return this location */

Quzah.

Quzah..

If you were in my shoes, would you put this on an exam as a question?

Originally posted by rjeff1804
Quzah..

If you were in my shoes, would you put this on an exam as a question?

It depends on how much you think they know. It took me a bit of time to follow the loop thread. I rewrote my explanation of it about three times. (Mainly because I was on the phone while I did it, but that aside, it's not the easiest thing to decypher.)

It's a good question in that it take time and logic to be able to figure out what it's doing. Once you actually follow the logic, it's quite clear as to what it's doing. It's just a ##### without comments to figure it out. Heh.

Again, it all depends on how much you think they know.

Quzah.

As a C instructor - for beginners I think this will be tough. If the students had the appropriate background before the question- arrays thats fine. If not be carefull!!!

If you want I can share with you my stuff questions quizzes etc. what I use in my C class. I teach it as a credit class at a college in the USA. Let me know