How would you use qsort to sort on a string

[Eddy C]

I'm curious if you can easily use qsort to sort the letters in a null
terminated string, without using any conditional statements?

char str[ ] = "bdace";

becomes "abcde"

 

[Ben Pfaff]

I'm curious if you can easily use qsort to sort the letters in a null
terminated string, without using any conditional statements?

char str[ ] = "bdace";

becomes "abcde"

The following is not compiled or well proofread. It will only
produce the desired output for your example on systems where
letters in alphabetical order have increasing character values
(which is "normal"):

int
compare_chars (const void *a_, const void *b_)
{
const char *a = (const char *) a_;
const char *b = (const char *) b_;

return *a < *b ? -1 : *a > *b;
}

qsort (str, strlen (str), 1, compare_chars);

 

[Kenneth Brody]

I'm curious if you can easily use qsort to sort the letters in a null
terminated string, without using any conditional statements?

char str[ ] = "bdace";

becomes "abcde"

Well, aside from the obvious "why would you want to do that" question (the
answer of which is probably "because that's what the homework assignment
said to do"), the answer is "yes, it can be done, but 'easily' is in the
eye of the beholder".

Replace:

if (char1 < char2)
compare = -1;
else if ( char1 > char2 )
compare = 1;
else
compare = 0;

with:

int cmp[3] = { -1,0,1 };
compare = cmp[signum(char1-char2)+1];

Implementing signum() without conditionals is left as an exercise to the
reader.

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:[email protected]>

 

[Artie Gold]

I'm curious if you can easily use qsort to sort the letters in a null
terminated string, without using any conditional statements?

char str[ ] = "bdace";

becomes "abcde"

The following is not compiled or well proofread. It will only
produce the desired output for your example on systems where
letters in alphabetical order have increasing character values
(which is "normal"):

int
compare_chars (const void *a_, const void *b_)
{
const char *a = (const char *) a_;

Why the cast?

const char *b = (const char *) b_;
Similarly...

return *a < *b ? -1 : *a > *b;

....and isn't this a `conditional expression'?

}

qsort (str, strlen (str), 1, compare_chars);

I guess one could get *really* devious with something like:

#include <string.h>
int
compare_chars(const void *a_, const void *b_)
{
static char a[2], b[2];
a[0] = *(char *)a_;
b[0] = *(char *)b_;
return strcoll(a, b);
}

...but that would be *wrong* wouldn;t it?

--ag

 

[Eddy C]

not a homework assignment, just comparing languages.

 

[Eric Sosman]

Ben Pfaff wrote On 02/09/06 13:02,:

I'm curious if you can easily use qsort to sort the letters in a null
terminated string, without using any conditional statements?

char str[ ] = "bdace";

becomes "abcde"

The following is not compiled or well proofread. It will only
produce the desired output for your example on systems where
letters in alphabetical order have increasing character values
(which is "normal"):

int
compare_chars (const void *a_, const void *b_)
{
const char *a = (const char *) a_;
const char *b = (const char *) b_;

return *a < *b ? -1 : *a > *b;

To avoid the conditional operator (in pursuit of
the goal of "no conditional statements,") I'd suggest

return (*a > *b) - (*a < *b);

 

[Kenneth Brody]

not a homework assignment, just comparing languages.

(Someone else will shortly post the URL on how to properly post using
Google's broken news interface.)

[... how to use qsort without using conditional statements ...]

Still, the question of "why would you want to do that" applies.

"I'm comparing automobiles, and want to know how to get your car to
accellerate without moving the pistons."

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:[email protected]>

 

[Eddy C]

We were debating how simple it would be to write a function that counts
the number of lower case a's in a null terminated string without using
strlen, conditional logic and recursion. We came up with a few
approaches and thought the sort one was pretty funny and very opaque.
I'm not the C guy though.

int res;
char set[] = "a";

qsort(str,sizeof(str)-1,1,cmp);
res = strcspn(s,set)-strspn(s,set);

 

[Eddy C]

Why, here are few reasons. Interview questions and seeing how someone
breaksdown the problem. I think its a pretty dumb question myself,
because you wouldn't run into that problem in the real world.

 

[Eric Sosman]

Eddy C wrote On 02/09/06 14:50,:

Why, here are few reasons. Interview questions and seeing how someone
breaksdown the problem. I think its a pretty dumb question myself,
because you wouldn't run into that problem in the real world.

Why not? It might be useful in part of an anagram
generator, for instance.

 

[Eddy C]

fair point, though I don't have many projects that require no
conditional logic.

 

[Ben Pfaff]

Why the cast?

Not thinking very clearly this morning. It is unnecessary and
should be omitted.

...and isn't this a `conditional expression'?

It is not a "conditional statement" as far as I know. However, I
don't what a conditional statement is for sure; I assumed it
meant an "if" statement.

 

[CBFalconer]

(Someone else will shortly post the URL on how to properly post using
Google's broken news interface.)

Alright. See my sig. below.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

 

[Kenneth Brody]

Eddy C wrote On 02/09/06 14:50,:

Why not? It might be useful in part of an anagram
generator, for instance.

The question wasn't "how do I sort the letters in a string", but rather
"how do I do it without conditional statements". (See the original post,
not the thread subject.)

You would probably want to use conditional statements in your anagram
generator for "the real world".

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:[email protected]>

 

[Ben Pfaff]

The question wasn't "how do I sort the letters in a string", but rather
"how do I do it without conditional statements". (See the original post,
not the thread subject.)

Furthermore, it was "how to do it without conditional statements
using qsort()". It's also easy to do it without conditional
statements without qsort(), given a few assumptions normally
reasonable on a hosted implementation. Here's a sample that,
given that I haven't been writing much in comp.lang.c lately, is
probably full of bugs; have fun:

void
sort_string (char *s)
{
size_t counts[UCHAR_MAX + 1] = { 0 };
char *p;
int i;

for (p = s; *p != '\0'; p++)
counts[(unsigned char) *p]++;

p = s;
for (i = 0; i <= UCHAR_MAX; i++) {
size_t j;
for (j = 0; j < counts; j++)
*p++ = i;
}
}

 

[Keith Thompson]

(Someone else will shortly post the URL on how to properly post using
Google's broken news interface.)

I live to serve.

<http://cfaj.freeshell.org/google/>

Eddy, please read that web page before posting here again. Thanks.

 

[Mark McIntyre]

Why, here are few reasons.

A few reasons for what? Please read this:

 

[Eddy C]

Sorry, don't normally use this client. I admit its pretty stupid
design, if that's the default behaviour.

 

[Nelu]

Sorry, don't normally use this client. I admit its pretty stupid
design, if that's the default behaviour.

Then don't repeat the mistake
Read what Keith told you to read.

 

[Eddy C]

Then don't repeat the mistake
Read what Keith told you to read.

I guess sarcasm is somewhat of an aquired taste. Anyway this is very
far removed from the original topic, which was described at the very
beginning.

eddy73

I'm curious if you can easily use qsort to sort the letters in a null
terminated string, without using any conditional statements?

and the follow on questions of -

Kenneth Brody