Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
March 7th, 2005, 01:17 AM
 thall89553
Contributing User

Join Date: Jan 2004
Location: Budapest
Posts: 1,702
Time spent in forums: 5 Days 18 h 56 m 37 sec
Reputation Power: 66
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:
Quote:
 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>

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;
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
March 7th, 2005, 04:18 AM
 Ancient Dragon
Contributing User

Join Date: Jan 2004
Location: near St. Louis Illinois
Posts: 3,288
Time spent in forums: 1 Week 2 Days 20 h 37 m 22 sec
Reputation Power: 23
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/

#3
March 7th, 2005, 04:58 AM
 guggach
Contributing User

Join Date: Jul 2004
Location: Middle Europa
Posts: 1,200
Time spent in forums: 1 Week 1 Day 11 h 47 m 52 sec
Reputation Power: 13
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.

#4
March 7th, 2005, 05:06 AM
 thall89553
Contributing User

Join Date: Jan 2004
Location: Budapest
Posts: 1,702
Time spent in forums: 5 Days 18 h 56 m 37 sec
Reputation Power: 66
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?

#5
March 7th, 2005, 05:57 AM
 guggach
Contributing User

Join Date: Jul 2004
Location: Middle Europa
Posts: 1,200
Time spent in forums: 1 Week 1 Day 11 h 47 m 52 sec
Reputation Power: 13
Quote:
 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.
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)```

have fun

Last edited by guggach : March 7th, 2005 at 06:00 AM.

#6
March 7th, 2005, 07:22 AM
 DaWei_M
Lord of Dorkness

Join Date: Jan 2004
Location: Central New York. Texan via Arizona, out of his element!
Posts: 8,521
Time spent in forums: 4 Weeks 20 h 13 m 16 sec
Warnings Level: 20
Number of bans: 3
Reputation Power: 3268
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.
DaWei on Pointers Politically Incorrect.

#7
March 7th, 2005, 07:48 AM
 mitakeet
I'm Baaaaaaack!

Join Date: Jul 2003
Location: Maryland
Posts: 5,538
Time spent in forums: 2 Weeks 4 Days 2 h 38 m 46 sec
Reputation Power: 243
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.

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

#8
March 7th, 2005, 03:44 PM
 clifford
Contributing User

Join Date: Aug 2003
Location: UK
Posts: 4,965
Time spent in forums: 1 Month 4 Days 3 h 25 m 35 sec
Reputation Power: 1801
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.

#9
March 7th, 2005, 04:06 PM
 EverLearning
the ^ user

Join Date: May 2004
Location: f(x)
Posts: 365
Time spent in forums: 3 Days 3 h 51 m 44 sec
Reputation Power: 12
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.

#10
March 7th, 2005, 05:18 PM
 Scorpions4ever
Banned ;)

Join Date: Nov 2001
Location: Woodland Hills, Los Angeles County, California, USA
Posts: 9,535
Time spent in forums: 2 Months 3 Days 5 h 32 m 8 sec
Reputation Power: 4106
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

#11
March 8th, 2005, 04:28 AM
 etienne141
Paris est magique!

Join Date: Apr 2004
Location: France!
Posts: 370
Time spent in forums: 5 Days 21 h 56 m 30 sec
Reputation Power: 95
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

#12
March 8th, 2005, 11:52 AM
 jubitzu
Contributing User

Join Date: Jan 2004
Posts: 743
Time spent in forums: 21 h 16 m 10 sec
Warnings Level: 10
Number of bans: 1
Reputation 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.

#13
March 8th, 2005, 02:23 PM
 clifford
Contributing User

Join Date: Aug 2003
Location: UK
Posts: 4,965
Time spent in forums: 1 Month 4 Days 3 h 25 m 35 sec
Reputation Power: 1801
Quote:
 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:
Quote:
 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.

#14
March 8th, 2005, 02:35 PM
 sunbear2
Contributing User

Join Date: Feb 2004
Location: Tennessee
Posts: 73
Time spent in forums: 4 h 4 m 59 sec
Reputation Power: 10
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.

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Teacher wants source Code of qsort function????