Thread: sort problem for an exam

  1. #1
    Registered User
    Join Date
    Jan 2003
    Posts
    11

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

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  3. #3
    Registered User
    Join Date
    Jan 2003
    Posts
    11
    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

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Jan 2003
    Posts
    11
    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!

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Jan 2003
    Posts
    11
    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.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    Jan 2003
    Posts
    11
    Quzah..

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

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  11. #11
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511

    Talking

    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
    Mr. C: Author and Instructor

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using Vectors (cont) - Sort Problem
    By clegs in forum C++ Programming
    Replies: 2
    Last Post: 09-17-2007, 06:31 AM
  2. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  3. array sort output problem
    By radiantarchon28 in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2007, 01:49 AM
  4. Problem with Bubble Sort code
    By lisa1234 in forum C++ Programming
    Replies: 7
    Last Post: 01-13-2004, 03:40 PM
  5. Decending Sort Problem
    By SledMan2002 in forum C Programming
    Replies: 4
    Last Post: 10-26-2002, 06:07 PM