March 7th, 2005, 01:17 AM

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[len1] == '\n'){
data[len1] = '\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...
March 7th, 2005, 04:18 AM

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/
March 7th, 2005, 04:58 AM

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 hyperfast
* insertion sort. For each remaining element, min, from [1] to [n1],
* 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 inline, which is spacelosing but timesaving.
* (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);
}
}
/*
* Semistandard 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[59], preferred languages french and C.
March 7th, 2005, 05:06 AM

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...
March 7th, 2005, 05:57 AM

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 06:00 AM.
working on Solaris[59], preferred languages french and C.
March 7th, 2005, 07:22 AM

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.
March 7th, 2005, 07:48 AM

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 5001000 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.
March 7th, 2005, 03:44 PM

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 05:34 PM.
March 7th, 2005, 04:06 PM

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 decentlylooking tutorials and they produced wrong output, actually it was quicksort that was not working for several cases.
March 7th, 2005, 05:18 PM

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
March 8th, 2005, 04:28 AM

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 subarrays: one with elements smaller than the pivot, one with the greater ones
(You could make an another function for it)
You qsort recursively both subarrays
You concatenate the results with the pivot between the two sorted subarrays
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
March 8th, 2005, 11:52 AM

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.
March 8th, 2005, 02:23 PM

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.
March 8th, 2005, 02:35 PM

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