### Thread: Teacher wants source Code of qsort function????

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>

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?
2. 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. 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);
}```
4. 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?
5. 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.
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 05:00 AM.
6. 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.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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. No Profile Picture
Contributing User
Devshed Novice (500 - 999 posts)

Join Date
Jan 2004
Location
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.
13. 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.
14. 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. ;)