code Critics please..

[herrcho]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void select_sort(void *base, size_t nelem, size_t width, int (*fcmp)
(const void *, const void *))
{
void *min;
int minindex;
int i,j;
min = malloc(width);

for (i = 0;i < nelem-1 ;i++ )
{
minindex = i;
memcpy(min, (char *)base + i*width, width); /* min = a */
for (j=i+1; j < nelem ;j++ )
{
if (fcmp(min, (char *)base + j*width)>0 ) /* if (min >
a[j]) */
{
memcpy(min, (char *)base + j*width, width); /* min = a[j]
*/
minindex = j;
}
}
memcpy((char*) base + minindex*width, (char *)base + i*width, width);

/* a[minindex] = a */

memcpy((char *)base + i*width, min, width); /* a = min */
}
free(min);
}

int intcmp(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}

int main()
{
char a[] = "wonderful";
select_sort(a,strlen(a),sizeof(char),intcmp );
puts(a);

return 0;
}

i made the above using 'Selection Sort' ..

but it outputs wrong.. it should print "deflnoruw" but just prints
"wonderful"

Could anyone explain to me ? Any comments would be appreciated.. ^^

 

[Allan Bruce]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void select_sort(void *base, size_t nelem, size_t width, int (*fcmp)
(const void *, const void *))
{
void *min;
int minindex;
int i,j;
min = malloc(width);

for (i = 0;i < nelem-1 ;i++ )
{
minindex = i;
memcpy(min, (char *)base + i*width, width); /* min = a */
for (j=i+1; j < nelem ;j++ )
{
if (fcmp(min, (char *)base + j*width)>0 ) /* if (min >
a[j]) */
{
memcpy(min, (char *)base + j*width, width); /* min = a[j]
*/
minindex = j;
}
}
memcpy((char*) base + minindex*width, (char *)base + i*width, width);

/* a[minindex] = a */

memcpy((char *)base + i*width, min, width); /* a = min */
}
free(min);
}

int intcmp(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}

int main()
{
char a[] = "wonderful";
select_sort(a,strlen(a),sizeof(char),intcmp );
puts(a);

return 0;
}

i made the above using 'Selection Sort' ..

but it outputs wrong.. it should print "deflnoruw" but just prints
"wonderful"

Could anyone explain to me ? Any comments would be appreciated.. ^^

Comments from you would be appreciated too. Whilst it is easy for you to
run through the code, it can be difficult to see your reasoning and flow of
thought. A few small comments would not go amiss and people would be more
inclined to help you.
Allan

 

[Jens.Toerring]

int intcmp(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}

int main()
{
char a[] = "wonderful";
select_sort(a,strlen(a),sizeof(char),intcmp );

sizeof(char) == 1 by definition.

When you want to compare characters you also need to use a function to
compare characters and not ints. Now you're always comparing sets of
several characters (how many depends on sizeof(int) on your machine).
Thus you're probably also guilty of accessing memory after the end of
your 'a' array. If you replace your intcmp() function by

int charcmp(const void *a, const void *b)
{
return ( int ) ( * ( char * ) a - * ( char * ) b );
}

everything works as expected:

jens@crowley:~/TESTS> allans_selsort
deflnoruw
jens@crowley:~/TESTS>
Regards, Jens
--
_ _____ _____
| ||_ _||_ _| (e-mail address removed)-berlin.de
_ | | | | | |
| |_| | | | | | http://www.physik.fu-berlin.de/~toerring
\___/ens|_|homs|_|oerring

 

[CBFalconer]

.... snip ...

int intcmp(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}
.... snip ...

i made the above using 'Selection Sort' ..

but it outputs wrong.. it should print "deflnoruw" but just prints
"wonderful"

Could anyone explain to me ? Any comments would be appreciated.. ^^

I removed the rest, because it is very hard to read with the
overlength lines and use of excessive indentation. Don't use tabs
in your source, use spaces. Keep the line length under 72 chars.

Now to the heart of the problem - You are sorting chars, but
comparing ints! The comparison function is supplied by the caller
for a reason, only the caller knows the type of the sorted items.
So I suggest:

int intcmp(const void *a, const void *b)
{
char *ac = a; /* No extraneous casts needed */
char *bc = b;

return (*ac > *bc) - (*ac < *bc);
}

avoiding all overflows, and returning 1, 0 , -1. Works for all
integer types by simply changing the type of ac and bc.

 

[David Rubin]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void select_sort(void *base, size_t nelem, size_t width, int (*fcmp)
(const void *, const void *))
{
void *min;
int minindex;
int i,j;

unsigned char *beg = base;
unsigned char *end = beg + nelem * width; /* one elt past end of
array */
unsigned char *ith;
unsigned char *jth;
unsigned char *min;
unsigned char *tmp;

min = malloc(width);

You don't need to allocate min, but you might allocate tmp...

for (i = 0;i < nelem-1 ;i++ )
{
minindex = i;
memcpy(min, (char *)base + i*width, width); /* min = a */

How about

ith = beg + i * width;
min = ith; /* POINT to the minimum element */

for (j=i+1; j < nelem ;j++ )
{
if (fcmp(min, (char *)base + j*width)>0 ) /* if (min > a[j]) */

See comments elsethread about intcmp vs charcmp.

{
memcpy(min, (char *)base + j*width, width); /* min = a[j] */

min = (unsigned char *)base + j * width;

minindex = j;

Don't need minindex.

}
}

Now that you've found the minimum element (a[m]), pointed to by min, you
can swap it with the ith element:

memcpy(tmp, ith, width); /* tmp = a */
memcpy(ith, min, width); /* a = a[m] */
memcpy(min, tmp, width); /* a[m] = tmp */

memcpy((char*) base + minindex*width, (char *)base + i*width, width);

/* a[minindex] = a */

memcpy((char *)base + i*width, min, width); /* a = min */
}
free(min);

free(tmp);

}

Also, it may be simpler to read the code if you compute pointers in your
loop statement rather than in the loop body. For example, the inner loop
might look like this:

for(jth = ith + width; jth < end; jth += width)
{
if(comp(min, jth) == 0) /* comp returns true/false */
min = jth;
}

Notice I changed fcmp to a predicate (comp). This is different than,
e.g., qsort, but a little cleaner in that the elements are ordered as
(a0,...,an) where comp(ai,ai+1) is true for i in [0..n]. (Incidentally,
you would want to change min to, e.g., kth, in the implementation to
remove the bias towards monotonically increasing sequences).

HTH,

/david

 

[Peter Nilsson]

....

Now to the heart of the problem - You are sorting chars, but
comparing ints! The comparison function is supplied by the caller
for a reason, only the caller knows the type of the sorted items.
So I suggest:

int intcmp(const void *a, const void *b)
{
char *ac = a; /* No extraneous casts needed */
char *bc = b;

return (*ac > *bc) - (*ac < *bc);
}

No casts, but it requires a diagnostic because you're discaring a const
qualifier. Making them const char * fill fix the diagnostic but it still
won't sort them properly if you prefer string characters to be sorted as
unsigned char [which is normally the case for me.]

int char_cmp(const void *a, const void *b)
{
const unsigned char *ac = a;
const unsigned char *bc = b;
return (*ac > *bc) - (*ac < *bc);
}