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]

"Eddy C" <ed****@gmail.com> writes:

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);
--
"The way I see it, an intelligent person who disagrees with me is
probably the most important person I'll interact with on any given
day."
--Billy Chambless

[Kenneth Brody]

Eddy C wrote:

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:Th*************@gmail.com>

[Artie Gold]

Ben Pfaff wrote:

"Eddy C" <ed****@gmail.com> writes:

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

--
Artie Gold -- Austin, Texas
http://goldsays.blogspot.com
http://www.cafepress.com/goldsays
"If you have nothing to hide, you're not trying!"

[Eddy C]

not a homework assignment, just comparing languages.

[Eric Sosman]

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

"Eddy C" <ed****@gmail.com> writes:

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

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

--
Er*********@sun.com

[Kenneth Brody]

Eddy C wrote:

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:Th*************@gmail.com>

[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.

--
Er*********@sun.com

[Eddy C]

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

[Ben Pfaff]

Artie Gold <ar*******@austin.rr.com> writes:

Ben Pfaff wrote:

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

Why the cast?

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

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

Similarly...

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

...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.
--
"When I have to rely on inadequacy, I prefer it to be my own."
--Richard Heathfield

[CBFalconer]

Kenneth Brody wrote:

Eddy C wrote:

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

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]

Eric Sosman wrote:

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.

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:Th*************@gmail.com>

[Ben Pfaff]

Kenneth Brody <ke******@spamcop.net> writes:

Eric Sosman wrote:

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.

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[i]; j++)
*p++ = i;
}
}

--
Bite me! said C.

[Keith Thompson]

Kenneth Brody <ke******@spamcop.net> writes:

Eddy C wrote:

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

I live to serve.

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

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

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Mark McIntyre]

On 9 Feb 2006 11:50:55 -0800, in comp.lang.c , "Eddy C"
<ed****@gmail.com> wrote:

Why, here are few reasons.

A few reasons for what? Please read this:
--
Please quote enough of the previous message for context. To do so from
Google, click "show options" and use the Reply shown in the expanded
header. For more information, please go here
<http://cfaj.freeshell.org/google/>
----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

[Eddy C]

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

[Nelu]

Eddy C wrote:

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.
--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)

[Eddy C]

Nelu wrote:

Eddy C wrote:

Sorry, don't normally use this client.
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"why would you want to do that"

[Jordan Abel]

On 2006-02-09, Kenneth Brody <ke******@spamcop.net> wrote:

Eric Sosman wrote:

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.

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

I think the answer that is wanted is to subtract the two characters for
the result of the comparison function. I.e. it's a question to see if
you "see" that solution

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

[Jordan Abel]

On 2006-02-09, Ben Pfaff <bl*@cs.stanford.edu> wrote:

Artie Gold <ar*******@austin.rr.com> writes:

Ben Pfaff wrote:

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

Why the cast?

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

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

Similarly...

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

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

I'd have used "return *b - *a", and i suspect that's the answer the
question is fishing for with the "no conditionals" thing.

[pete]

Jordan Abel wrote:

On 2006-02-09, Ben Pfaff <bl*@cs.stanford.edu> wrote:

Artie Gold <ar*******@austin.rr.com> writes:

Ben Pfaff wrote:
int
compare_chars (const void *a_, const void *b_)
{
const char *a = (const char *) a_;

Why the cast?

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

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

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

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

I'd have used "return *b - *a"

ITYM return *a - *b;

The type of (*a - *b) isn't guaranteed to be int,
it might be unsigned, in which case it won't work right.

--
pete

[Ben Pfaff]

Jordan Abel <ra*******@gmail.com> writes:

[for qsort() comparison function]

I'd have used "return *b - *a", and i suspect that's the answer the
question is fishing for with the "no conditionals" thing.

I wouldn't ever suggest using that form, because I've seen too
many people get bit by overflow using it. I've had multiple
people report "bugs" against GNU libavl, for example, when in
fact they used this trick in their comparison functions and that
caught up with them.
--
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

[Bill Gutz]

Ben Pfaff wrote:

Jordan Abel <ra*******@gmail.com> writes:

[for qsort() comparison function]

I'd have used "return *b - *a", and i suspect that's the answer the
question is fishing for with the "no conditionals" thing.

I wouldn't ever suggest using that form, because I've seen too
many people get bit by overflow using it. I've had multiple
people report "bugs" against GNU libavl, for example, when in
fact they used this trick in their comparison functions and that
caught up with them.

Right.

Search groups.google.com for "Kirby qsort". Here's a hit worth bookmarking:

http://tinyurl.com/duqc6

--
Bill

[CBFalconer]

Bill Gutz wrote:

.... snip ...
Search groups.google.com for "Kirby qsort". Here's a hit worth bookmarking:

http://tinyurl.com/duqc6

No so called tinyurl is worth bookmarking. They become obsolete,
and even worse, they give no indication of their eventual
destination. Supply a real URL instead.

--
"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/>

[nicholas.wakefield]

> > The question wasn't "how do I sort the letters in a string", but rather

"how do I do it without conditional statements"

I'm not sure what you define as conditional but for loops are
considered a conditional loop to me for (p = s; *p != '\0'; p++)
for (i = 0; i <= UCHAR_MAX; i++) {
for (j = 0; j < counts[i]; j++)

You don't have to use qsort to solve the problem, it was one of many
ways we though of.

[Jordan Abel]

On 2006-02-10, CBFalconer <cb********@yahoo.com> wrote:

Bill Gutz wrote:

... snip ...

Search groups.google.com for "Kirby qsort". Here's a hit worth bookmarking:

http://tinyurl.com/duqc6

No so called tinyurl is worth bookmarking. They become obsolete,
and even worse, they give no indication of their eventual
destination. Supply a real URL instead.

What i've heard is "good practice" is to include both a shortened
version and the real one, in case someone's newsreader can't handle the
real one due to it being too wide

[Keith Thompson]

CBFalconer <cb********@yahoo.com> writes:

Bill Gutz wrote:

... snip ...

Search groups.google.com for "Kirby qsort". Here's a hit worth bookmarking:

http://tinyurl.com/duqc6

No so called tinyurl is worth bookmarking. They become obsolete,
and even worse, they give no indication of their eventual
destination. Supply a real URL instead.

<OT>
I wasn't aware that they can become obsolete (the tinyurl.com home
page doesn't say anything about that); I've always assumed they last
indefinitely. Your other pointers are valid, though. Also,
tinyurl.com advertises the use of their service to hide affiliate
URLs, which doesn't seem entirely ethical.
</OT>

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Bill Gutz]

CBFalconer wrote:

Bill Gutz wrote:

... snip ...

Search groups.google.com for "Kirby qsort". Here's a hit worth bookmarking:

http://tinyurl.com/duqc6

No so called tinyurl is worth bookmarking. They become obsolete,
and even worse, they give no indication of their eventual
destination. Supply a real URL instead.

Sorry. I apologize. Please forgive me. Here is the real URL:

http://groups.google.com/group/comp....673e0c03bce719

[CBFalconer]

Bill Gutz wrote:

CBFalconer wrote:

Bill Gutz wrote:

... snip ...

Search groups.google.com for "Kirby qsort". Here's a hit worth bookmarking:

http://tinyurl.com/duqc6

No so called tinyurl is worth bookmarking. They become obsolete,
and even worse, they give no indication of their eventual
destination. Supply a real URL instead.

Sorry. I apologize. Please forgive me. Here is the real URL:

http://groups.google.com/group/comp....673e0c03bce719

No apology needed. My purpose was to advise about the situation.
Nobody is expected to know everything or even to draw all the
possible conclusions. The combination (short/long) provides the
best of both worlds.

--
"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/>

[Jordan Abel]

On 2006-02-12, CBFalconer <cb********@yahoo.com> wrote:

Bill Gutz wrote:

CBFalconer wrote:

Bill Gutz wrote:

... snip ...

Search groups.google.com for "Kirby qsort". Here's a hit worth bookmarking:

http://tinyurl.com/duqc6

No so called tinyurl is worth bookmarking. They become obsolete,
and even worse, they give no indication of their eventual
destination. Supply a real URL instead.

Sorry. I apologize. Please forgive me. Here is the real URL:

http://groups.google.com/group/comp....673e0c03bce719

No apology needed. My purpose was to advise about the situation.
Nobody is expected to know everything or even to draw all the
possible conclusions. The combination (short/long) provides the
best of both worlds.

When linking a google groups message, it might make sense to figure out
the old ?selm=Message-ID representation [which still works] - mainly
because it provides a reference point that does not depend on google
groups still existing in the future.