#1
  1. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jan 2004
    Location
    Budapest
    Posts
    1,703
    Rep Power
    68

    Teacher wants source Code of qsort function????


    Please help me, I have an A riding on this question. I turned in an assignment for school whereas I was asked to get 8 integers from an individual and then sort them in descending order. With the assistance of some great people in this forum, I was able to do that. NOW, I get my grade back and here are my teacher's comments:
    Although your week 5 program works, you used provided qsort function. The purpose of this assignment is to ask you to figure out the way of how to sort numbers. I know you are going to argue that I did not indicate that you cannot use qsort function. If you include the source code of qsort function in your code, this will be acceptable.
    So, I am gathering from that that if I resubmit with the "source code" for the qsort function, he will modify my grade. Ok, so here is the assignment I turned in. If ANYONE can help me out, I would be so grateful...

    Code:
    #include <ctype.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    int read_nums(int *array) {
        char data[80];
        int i, inc=0, len;
        puts("\nEnter 8 Integers to be Sorted in Descending Order\n");
        while (inc < 8){
            printf("Enter Integer #%d and Press Enter ==> ", inc+1);
            fgets(data, 80, stdin);/* Get Integer */
            len = strlen(data);
            if (data[len-1] == '\n'){
                data[len-1] = '\0';
                len--;
            }
            for (i=0; i<len; i++){
                if (!isdigit(data[i])){
                    printf("Sorry, not an Integer - try again please.\n");
                    break;
                }
            }
            if (i==len)
                array[inc++] = atoi(data);
        }
    
        return inc;
    }
    
    void display_nums(int *array) {
        int i;
        printf("\nEntered Integers in descending order are  ");
        for (i=8; i>0; i--)
            printf("%d ", array[i - 1]);
        printf("\n");
    }
    
    int comp_nums(const int *num1, const int *num2) {
        if (*num1 < *num2) return -1;
        if (*num1 > *num2) return 1;
        return 0;
    }
    int main() {
        int numbers[8];
        int how_many=8;
        read_nums(numbers);
        qsort(numbers, how_many, sizeof(int), (void *)comp_nums);
        display_nums(numbers);
        return 0;
    }
    I Googled qsort source code and nothing came up really clear for me. I am assuming that what he is looking for is that I actually put the qsort function into the program. Is that what you take from his comment?
    Today the world, tomorrow the universe...
  2. #2
  3. Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    Jan 2004
    Location
    near St. Louis Illinois
    Posts
    3,288
    Rep Power
    25
    I take it that your instructor wants you to write your own sorting algorithm and not use one of the standard library functions. There are quite a few algorithms that you could use. google for "quicker sort" or "sort algorithms". Here are some for java

    http://cg.scs.carleton.ca/~morin/misc/sortalg/
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Jul 2004
    Location
    Middle Europa
    Posts
    1,200
    Rep Power
    15
    an old still working version
    Code:
    #if !defined(lint) && defined(SCCSIDS)
    static	char sccsid[] = "@(#)qsort.c 1.1 90/03/23"; /* from UCB 4.2 83/03/089 */
    #endif
    
    /*
     * qsort.c:
     * Our own version of the system qsort routine which is faster by an average
     * of 25%, with lows and highs of 10% and 50%.
     * The THRESHold below is the insertion sort threshold, and has been adjusted
     * for records of size 48 bytes.
     * The MTHREShold is where we stop finding a better median.
     */
    
    #define		THRESH		4		/* threshold for insertion */
    #define		MTHRESH		6		/* threshold for median */
    
    static  int		(*qcmp)();		/* the comparison routine */
    static  int		qsz;			/* size of each record */
    static  int		thresh;			/* THRESHold in chars */
    static  int		mthresh;		/* MTHRESHold in chars */
    
    /*
     * qsort:
     * First, set up some global parameters for qst to share.  Then, quicksort
     * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
     * It's not...
     */
    
    qsort(base, n, size, compar)
    	char	*base;
    	int	n;
    	int	size;
    	int	(*compar)();
    {
    	register char c, *i, *j, *lo, *hi;
    	char *min, *max;
    
    	if (n <= 1)
    		return;
    	qsz = size;
    	qcmp = compar;
    	thresh = qsz * THRESH;
    	mthresh = qsz * MTHRESH;
    	max = base + n * qsz;
    	if (n >= THRESH) {
    		qst(base, max);
    		hi = base + thresh;
    	} else {
    		hi = max;
    	}
    	/*
    	 * First put smallest element, which must be in the first THRESH, in
    	 * the first position as a sentinel.  This is done just by searching
    	 * the first THRESH elements (or the first n if n < THRESH), finding
    	 * the min, and swapping it into the first position.
    	 */
    	for (j = lo = base; (lo += qsz) < hi; )
    		if (qcmp(j, lo) > 0)
    			j = lo;
    	if (j != base) {
    		/* swap j into place */
    		for (i = base, hi = base + qsz; i < hi; ) {
    			c = *j;
    			*j++ = *i;
    			*i++ = c;
    		}
    	}
    	/*
    	 * With our sentinel in place, we now run the following hyper-fast
    	 * insertion sort.  For each remaining element, min, from [1] to [n-1],
    	 * set hi to the index of the element AFTER which this one goes.
    	 * Then, do the standard insertion sort shift on a character at a time
    	 * basis for each element in the frob.
    	 */
    	for (min = base; (hi = min += qsz) < max; ) {
    		while (qcmp(hi -= qsz, min) > 0)
    			/* void */;
    		if ((hi += qsz) != min) {
    			for (lo = min + qsz; --lo >= min; ) {
    				c = *lo;
    				for (i = j = lo; (j -= qsz) >= hi; i = j)
    					*i = *j;
    				*i = c;
    			}
    		}
    	}
    }
    
    /*
     * qst:
     * Do a quicksort
     * First, find the median element, and put that one in the first place as the
     * discriminator.  (This "median" is just the median of the first, last and
     * middle elements).  (Using this median instead of the first element is a big
     * win).  Then, the usual partitioning/swapping, followed by moving the
     * discriminator into the right place.  Then, figure out the sizes of the two
     * partions, do the smaller one recursively and the larger one via a repeat of
     * this code.  Stopping when there are less than THRESH elements in a partition
     * and cleaning up with an insertion sort (in our caller) is a huge win.
     * All data swaps are done in-line, which is space-losing but time-saving.
     * (And there are only three places where this is done).
     */
    
    static
    qst(base, max)
    	char *base, *max;
    {
    	register char c, *i, *j, *jj;
    	register int ii;
    	char *mid, *tmp;
    	int lo, hi;
    
    	/*
    	 * At the top here, lo is the number of characters of elements in the
    	 * current partition.  (Which should be max - base).
    	 * Find the median of the first, last, and middle element and make
    	 * that the middle element.  Set j to largest of first and middle.
    	 * If max is larger than that guy, then it's that guy, else compare
    	 * max with loser of first and take larger.  Things are set up to
    	 * prefer the middle, then the first in case of ties.
    	 */
    	lo = max - base;		/* number of elements as chars */
    	do	{
    		mid = i = base + qsz * ((lo / qsz) >> 1);
    		if (lo >= mthresh) {
    			j = (qcmp((jj = base), i) > 0 ? jj : i);
    			if (qcmp(j, (tmp = max - qsz)) > 0) {
    				/* switch to first loser */
    				j = (j == jj ? i : jj);
    				if (qcmp(j, tmp) < 0)
    					j = tmp;
    			}
    			if (j != i) {
    				ii = qsz;
    				do	{
    					c = *i;
    					*i++ = *j;
    					*j++ = c;
    				} while (--ii);
    			}
    		}
    		/*
    		 * Semi-standard quicksort partitioning/swapping
    		 */
    		for (i = base, j = max - qsz; ; ) {
    			while (i < mid && qcmp(i, mid) <= 0)
    				i += qsz;
    			while (j > mid) {
    				if (qcmp(mid, j) <= 0) {
    					j -= qsz;
    					continue;
    				}
    				tmp = i + qsz;	/* value of i after swap */
    				if (i == mid) {
    					/* j <-> mid, new mid is j */
    					mid = jj = j;
    				} else {
    					/* i <-> j */
    					jj = j;
    					j -= qsz;
    				}
    				goto swap;
    			}
    			if (i == mid) {
    				break;
    			} else {
    				/* i <-> mid, new mid is i */
    				jj = mid;
    				tmp = mid = i;	/* value of i after swap */
    				j -= qsz;
    			}
    		swap:
    			ii = qsz;
    			do	{
    				c = *i;
    				*i++ = *jj;
    				*jj++ = c;
    			} while (--ii);
    			i = tmp;
    		}
    		/*
    		 * Look at sizes of the two partitions, do the smaller
    		 * one first by recursion, then do the larger one by
    		 * making sure lo is its size, base and max are update
    		 * correctly, and branching back.  But only repeat
    		 * (recursively or by branching) if the partition is
    		 * of at least size THRESH.
    		 */
    		i = (j = mid) + qsz;
    		if ((lo = j - base) <= (hi = max - i)) {
    			if (lo >= thresh)
    				qst(base, j);
    			base = i;
    			lo = hi;
    		} else {
    			if (hi >= thresh)
    				qst(i, max);
    			max = j;
    		}
    	} while (lo >= thresh);
    }
    working on Solaris[5-9], preferred languages french and C.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jan 2004
    Location
    Budapest
    Posts
    1,703
    Rep Power
    68

    Thank you.


    This is great, a bit above my head, but great. Question: Can I just plug this into my program as it is presented up above?
    Today the world, tomorrow the universe...
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Jul 2004
    Location
    Middle Europa
    Posts
    1,200
    Rep Power
    15
    Originally Posted by thall89553
    This is great, a bit above my head, but great. Question: Can I just plug this into my program as it is presented up above?
    yes, not very difficult but laborious.
    dont include, make an object and link it w/ your prog
    so you can reuse it in other projects.
    you sure need forwards declarations and ....
    at least make some changes (coustomize)
    avoid possible side effects, rewrite things like:
    Code:
    	for (min = base; (hi = min += qsz) < max; ) {
    		while (qcmp(hi -= qsz, min) > 0)
    think about how you will present that code to your prof
    have fun
    Last edited by guggach; March 7th, 2005 at 05:00 AM.
    working on Solaris[5-9], preferred languages french and C.
  10. #6
  11. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3315
    I would suggest that your professor want you to have wrapped your head around a sorting process, even if it's the most inefficient kind of bubble one might devise.
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
  12. #7
  13. I'm Baaaaaaack!
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Jul 2003
    Location
    Maryland
    Posts
    5,538
    Rep Power
    245
    Just a short note on bubble sort vs qsort (or any other). If you have a small number of elements (in my experiments in the past, 'small' was 500-1000 elements), the bubble sort is just as fast or faster than qsort, so just because bubble sort is deemed sloppy and inefficient by sorting experts, it is a perfect solution for small problems.

    My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
    Free code: http://sol-biotech.com/code/.
    Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
    Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
    LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

    It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
    --Me, I just made it up

    The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
    --George Bernard Shaw
  14. #8
  15. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,119
    Rep Power
    1803
    It seems probable to me that your prof. will recognise that you cribbed this code from elsewhere.

    I think that he has continued to be unclear, because I cannot believe that he really meant you to simply reproduce the source to the library code.

    If you really want that 'A', you will need ot do a little more work that that. I doubt that he is looking for an elegant or efficient algorithim, just some evidence that you know how to manipulate data.

    Because qsort uses a pointer to the compare function, I suggest that you produce something simpler and less generic in this case - specific to sorting integers.

    Clifford
    Last edited by clifford; March 7th, 2005 at 04:34 PM.
  16. #9
  17. No Profile Picture
    the ^ user
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2004
    Location
    f(x)
    Posts
    365
    Rep Power
    14
    A note from experience on the quicksort: TEST ALL CONDITIONS!!! do not blindly copy from what you find on google. I found a few algorithms put out by decently-looking tutorials and they produced wrong output, actually it was quicksort that was not working for several cases.
  18. #10
  19. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,710
    Rep Power
    4273
    You could tell the teacher that there are plenty of qsort source code routines on the web. For example, Free, Net and Open BSD all make their qsort source available on the web. Simply point your teacher to that source.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  20. #11
  21. Paris est magique!
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2004
    Location
    France!
    Posts
    370
    Rep Power
    97
    I don't think that the purpose of an algo. course is to get source code from the Web; especially using sorting functions in an assignement about sorting...

    Let me just remind you the quick sort algorithm:

    you chose an element called the pivot (let us be simple: the first element of the array)

    You part the array into two sub-arrays: one with elements smaller than the pivot, one with the greater ones
    (You could make an another function for it)

    You qsort recursively both sub-arrays

    You concatenate the results with the pivot between the two sorted sub-arrays

    And it's done!

    (Btw: we clearly see here that its cost is O(n*ln(n)) )

    Shouldn't be too hard? try it and post if you still have problems
  22. #12
  23. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Jan 2004
    Location
    Colorful Colorado
    Posts
    743
    Rep Power
    0
    i am amazed that your instructor did not recognize that you used the qsort function from the library. you could simply tell him that is what you did, then ask for an extra few days to code your own sort function.
  24. #13
  25. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,119
    Rep Power
    1803
    Originally Posted by jubitzu
    i am amazed that your instructor did not recognize that you used the qsort function from the library.
    I think he did, the OP quoted the tutor:
    Although your week 5 program works, you used provided qsort function.
    I assume that the tutor intended to ask him to do exactly that, although his English language seems rather ambiguous. Maybe however that is a problem of transcription.

    Clifford.
  26. #14
  27. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2004
    Location
    Tennessee
    Posts
    73
    Rep Power
    12

    try Bubble sort


    I think that the point of the course is not to use the libraries but to create a sorting mecanism for yourself. Take the array of numbers entered and
    check their values; print them back sorted. I sure that you can do it without qsort. In my first computer course they don't let us use the libraries, in my second course they did because we have other things to worry about, more complicated stuff. ;)

IMN logo majestic logo threadwatch logo seochat tools logo