Bubble Sort in C

[arnuld]

To sort an array of characters using Bubble-Sort algorithm.

WANTED: To sort an array using Bubble Sort algorithm
GOT: ..

Can I improve C implementation of this ? I got this algorithm from
section 8.2 of "Data Structures and Algorithms by Aho, Hopcraft and
Ullman". I was wondering if I could simply use pointers instead of those
integer couters and array indexing:


/* A C program to sort an array of characters using bubble sort algorithm
*
* VERSION 0.0
*
*/


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


void sort_bubble(char* );
void swap_elements(char*, char* );

int main(void)
{
char arrc[] = "heathfield";

printf("array(unsorted): %s\n", arrc);
sort_bubble(arrc);
printf("array(sorted): %s\n", arrc);

return 0;
}


void sort_bubble(char* c)
{
size_t i, j;
size_t s = strlen(c);

for(i = 0; i < s; ++i)
{
for(j = s-1; j != i; --j)
{
/* printf("c[%d] = %c, c[%d] = %c\n", j, c[j], j-1, c
[j-1]); */
if( c[j] < c[j-1] ) swap_elements( &c[j], &c[j-1]);
}
}
}



void swap_elements(char* c1, char* c2)
{
char temp = *c1;
*c1 = *c2;
*c2 = temp;
}
=============== OUTPUT ======================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra bubble-sort.c
[arnuld@dune programs]$ ./a.out
array(unsorted): heathfield
array(sorted): adeefhhilt
[arnuld@dune programs]$

 

[Julienne Walker]

To sort an array of characters using Bubble-Sort algorithm.

WANTED: To sort an array using Bubble Sort algorithm
GOT:   ..  

Can I improve C implementation of this ?  I got this algorithm from
section 8.2 of "Data Structures and Algorithms by Aho, Hopcraft and
Ullman". I was wondering if I could simply use pointers instead of those
integer couters and array indexing:

How would that be an improvement? You could probably shave off a few
cycles by optimizing the code, but an optimized bubble sort is still a
bubble sort. If you're using bubble sort on very small arrays, micro-
optimizations are unlikely to have any noticeable effect. If you're
using it on medium-sized or larger arrays, you can speed up the sort
operation drastically by using a more efficient algorithm.

 

[Mark Bluemel]

To sort an array of characters using Bubble-Sort algorithm.

WANTED: To sort an array using Bubble Sort algorithm
GOT:   ..  

Can I improve C implementation of this ?

What would you regard as an improvement?

Do you want to improve the aesthetics of the code? Its efficiency
(under what circumstances? with what size set of data? How unsorted do
you expect the data to be?)?

Adjusting the code to use pointers is fairly trivial, but it's not
clear that it's any kind of improvement. The swapping is done with
pointers anyway, and the loop structures are (IMHO) clearer referring
to arrays. I can't imagine that changing to pointers will affect
performance to any significant degree.

You might find it interesting to compare what you have with the
evolution of a (Shell) sort in K&R (pages 58, 108 and 116 of my copy
of the first edition).

 

[arnuld]

Do you want to improve the aesthetics of the code? Its efficiency
(under what circumstances? with what size set of data? How unsorted do
you expect the data to be?)?
.. SNIP..

Perhaps I need to be more clear. In this post, by improvement I meant:
"to improve the readability of the code, for me or the reader". Using
array indexing and int counters inside loops confuses me. In case of
pointers, I can use them for both: for loops and accessing array
elements (not sure about current case).

 

[bartc]

How would that be an improvement? You could probably shave off a few
cycles by optimizing the code, but an optimized bubble sort is still a
bubble sort. If you're using bubble sort on very small arrays, micro-
optimizations are unlikely to have any noticeable effect. If you're
using it on medium-sized or larger arrays, you can speed up the sort
operation drastically by using a more efficient algorithm.

I tested this non-optimised bubble sort with the built-in qsort.

The bubble sort was faster, for sorting "heathfield".

And this bubble-sort has scope for improvement, unlike the qsort.

Sometimes you want to sort small arrays, millions of times...

 

[Mark Bluemel]

Perhaps I need to be more clear. In this post, by improvement I meant:
"to improve the readability of the code, for me or the reader".

Ah. Well, for a start, I wouldn't let the sort routine rely on a null-
terminated string. I'd tell it how many elements need sorting.

So at the very least the prototype for "sort_bubble" should be
something like this:-

void sort_bubble(char array[], size_t n_elements);
or void sort_bubble(char *array, size_t n_elements); /* if you prefer
*/

Using array indexing and int counters inside loops confuses me.

It's very much the idiom in C, especially when the data we're working
with is clearly an array...

I personally dislike the use of single character variable names, in
most cases. Might the sort routine be clearer like this?

void sort_bubble(char array[], size_t n_elements)
{
size_t lower_bound = 0; /* leftmost element we are interested in */
size_t upper_bound = n_elements - 1; /* rightmost element we are
interested in */
size_t i; /* this single-character name is idiomatic for an array
index */

/* our outer loop moves the lower bound up the table */
for(lower_bound = 0; lower_bound < upper_bound; ++lower_bound)
{
/* our inner loop moves down the table to the lower bound
* sinking the smallest value to the bottom
*/
for(i = upper_bound; i != lower_bound; --i)
{
if( array < array[i-1] ) {
char temp = array;
array = array[i-1];
array[i-1] = temp;
}
}

}

 

[Ben Bacarisse]

I tested this non-optimised bubble sort with the built-in qsort.

The bubble sort was faster, for sorting "heathfield".

How odd. I did the same and found qsort to be much faster than the
bubble sort even on this short array. This is with a relatively
recent gcc and glibc.

 

[bartc]

How odd. I did the same and found qsort to be much faster than the
bubble sort even on this short array. This is with a relatively
recent gcc and glibc.

Maybe your qsort does a fast, internal bubblesort for small data?

My retests gave some mixed results, but I could still get bubblesort a
little faster using -O2 or -O3 of mingw/gcc. On -O1 they were about the
same, and on -O0, qsort was double the speed (but is an unfair test because
that's testing unoptimised code against presumably an optimised qsort
library function).

 

[user923005]

Maybe your qsort does a fast, internal bubblesort for small data?

My retests gave some mixed results, but I could still get bubblesort a
little faster using -O2 or -O3 of mingw/gcc. On -O1 they were about the
same, and on -O0, qsort was double the speed (but is an unfair test because
that's testing unoptimised code against presumably an optimised qsort
library function).

UNLESS
1. The list is very tiny (e.g. 20 items or less)
AND
2. The list is very nearly sorted already (e.g. 1 or 2 items in the
full list out of sequence)
THEN
Bubble sort is not only the wrong answer, it is tragically the wrong
answer.

Most of the time, for sorting a small list of items, insertion list is
a good choice.
Insertion sort is O(N*N) just like bubblesort, but the constant of
proportionality is much smaller.

For the rare condition list stated above, bubblesort is a good choice.
If you sort a large list of items with bubblesort -- well, you'll get
what's coming to you.

 

[user923005]

Perhaps I need to be more clear. In this post, by improvement I meant:
"to improve the readability of the code, for me or the reader". Using
array indexing and int counters inside loops confuses me. In case of
pointers, I can use them for both: for loops and accessing array
elements (not sure about current case).

Let me rephrase your question:
"How can I make my tractor compete with a forumla 1 racecar at Le
Mans?"

That's really what you are asking.

 

[osmium]

Let me rephrase your question:
"How can I make my tractor compete with a forumla 1 racecar at Le
Mans?"

That's really what you are asking.

I didn't see that at all. I saw it as a perfectly legitimate question from
someone who is in the process of learning to write computer programs.
Sadly, there are those rare individuals who were not born with a
pre-programmed ROM.

 

[Ben Bacarisse]

Maybe your qsort does a fast, internal bubblesort for small data?

I'd lay odds on it being insertion sort rather than bubble sort but I
imagine it does, yes.

 

[user923005]

I didn't see that at all.  I saw it as a perfectly legitimate question from
someone who is in the process of learning to write computer programs.
Sadly, there are those rare individuals who were not born with a
pre-programmed ROM.

I considered the question as legitimate.
Certainly equally legitimate to "What is the best way to polish a
Yak?"
Yet how valuable is it to polish a Yak?
Writing a better bubble sort is about as valuable as polishing a Yak.
Sure, once in a while there may be a "Who's got the shiniest Yak"
contest, but how often do the masses experience such a contest?

Bubble sort is so bad that I think it a terrible disservice that it is
a common choice in algorithms teaching courses, even though insertion
sort is easily just as simple and far more effective. Now, if bubble
sort is taught in an algorithms course as an example of "Don't do it
this way!" then I have no objection to its inclusion.

IMO-YMMV

 

[arnuld]

void sort_bubble(char *c)
{
size_t s = strlen(c) - 1;
char *const base = c;
char *const last = c + s;

while (s-- != 0) {
for (c = last; c != base; --c) {
if (c[-1] > c[0]) {
swap_elements(c, c - 1);
}
}

I haven't tried compiling it but it is very intelligent of you to produce
such a code. Short, concise and clear.

 

[arnuld]

Writing a better bubble sort is about as valuable as polishing a Yak.
Sure, once in a while there may be a "Who's got the shiniest Yak"
contest, but how often do the masses experience such a contest?

You are saying that the exercise I did was purely academic (not
practical). Remember I am not student anymore (neither I want to be),
I reply to interview questions like: "Will a C program compile if you
use #include inside a function ?" by using this answer: "I don't do
stupid things, why you want to put #include inside a function, even if
it works (which it does) what code in real-life contains this ?"

I am not thrashing you. I have academic exercises which theoretical to
the point of totally unrelated to the real world programming. So, if
you think my ways of learning algorithms are not practical, you must
have something better to offer.

Bubble sort is so bad that I think it a terrible disservice that it is
a common choice in algorithms teaching courses, even though insertion
sort is easily just as simple and far more effective.  Now, if bubble
sort is taught in an algorithms course as an example of "Don't do it
this way!" then I have no objection to its inclusion.

If other regular posters say that Bubble-Sort is inherently bad idea
(except of the 2 cases you mention in an earlier reply) then I will
not use in the code I write for my employer. BTW, next algorithm in
Ullman's book is insertion sort

 

[Mark]

void sort_bubble(char *c)
{
size_t s = strlen(c) - 1;

Why do you subtract 1? strlen doesn't include terminating 0.

 

[Seebs]

You are saying that the exercise I did was purely academic (not
practical).

Yes.

Because bubble-sort is bad enough that a good bubble-sort is still useless.

Remember I am not student anymore (neither I want to be),
I reply to interview questions like: "Will a C program compile if you
use #include inside a function ?" by using this answer: "I don't do
stupid things, why you want to put #include inside a function, even if
it works (which it does) what code in real-life contains this ?"

Oddly:

I have produced a hunk of code which does precisely that.

There's a hunk of machine-generated code, and it has a whole lot of
things of the form

int
foo(foo's arguments) {
// preamble happens here
#include guts/foo.c
// epilogue happens here
}

There are sound technical reasons for this. (Basically, the actual
declarations and preamble/epilogue are machine-generated and may change,
but the internals of each function are fairly stable.) But yes, it's
a real thing you might legitimately do. (I will say, though, that many
other aspects of that code aren't up to my personal standards; one of
my upcoming tasks is a substantial refactoring and rework. On the other
hand, it's been in production for something like six months with a single
genuine bug discovered, so it's at least working.)

I am not thrashing you. I have academic exercises which theoretical to
the point of totally unrelated to the real world programming. So, if
you think my ways of learning algorithms are not practical, you must
have something better to offer.

Yes.

To learn about algorithms, learn about O(n) notation, and find out what
the properties of algorithms are -- the most important thing, in general,
is to learn that the way you improve an algorithm is not generally with
peephole optimizations of a bad algorithm, but by choosing a better
algorithm.

For one of my articles on parallelization for Cell, I did an iterative
fractal system. Nice simple algorithm, had lots of interesting traits.
About two days of careful study of the architecture and hand-tweaking
some math library functions got me about a 30% speedup on the workloads
I could fit in the available memory on the platform.

There was one little quirk of the algorithm, which is that it ended up
producing pairs of the same point in some cases, and because this was an
iterative fractal, a couple of recursions later that might be 250 of that
same point. So I got curious, and put in half an hour tweaking the
algorithm to skip that duplicated point.

The net result was that I could do another depth of iteration before
running out of main memory, and performance was better by more than 50%
even for levels of recursion which fit in main memory before.

Which is to say, that half hour was dramatically more productive than the
previous two days.

If other regular posters say that Bubble-Sort is inherently bad idea
(except of the 2 cases you mention in an earlier reply) then I will
not use in the code I write for my employer. BTW, next algorithm in
Ullman's book is insertion sort

Bubble-sort is basically awful. It's certainly obvious, but it's also
extremely inefficient.

-s

 

[arnuld]

..SNIP..

There's a hunk of machine-generated code, and it has a whole lot of
things of the form

... SNIP...

I am *not* talking about machine. I am talking about the programmers,
the humans. So, I ask again, one should use #include sometimes not at
the top but at some other place in the program. That idea does not
look good to me

 

[Seebs]

I am *not* talking about machine.

The machine does what I tell it to.

As a programmer, I decided that the best way to implement something involved
putting #include statements inside functions.

The question is a lot more interesting than you might think. For instance,
I don't think it would be sensible to #include standard headers in a function.

I am talking about the programmers,
the humans. So, I ask again, one should use #include sometimes not at
the top but at some other place in the program. That idea does not
look good to me

And I'm telling you that, while in general that's probably right, there are
certainly cases where there are sound technical reasons to put a #include
inside a function body. It's not very common, but it's relevant.

Which is to say: If I'd gotten the answer you gave on an interview question,
I would have regarded it as a poor answer. I'd prefer to converse about it,
of course, rather than just getting a single static answer; there might be
good or bad arguments you could make for any given position on the issue. But
without anything else, calling something "stupid" and using this as a
justification not to know how or whether it works, or when it might not work,
would seem to me to be an answer which didn't show a great level of interest
in comprehending the language in general.

Since a lot of real-world work involves working with code other people
wrote, it's not usually enough to say "I wouldn't do that". You'll end up
working on code where someone else did.

-s

 

[user923005]

You are saying that the exercise I did was purely academic (not
practical). Remember I am not student anymore (neither I want to be),
I reply to interview questions like: "Will a C program compile if you
use #include inside a function ?" by using this answer: "I don't do
stupid things, why you want to put #include inside a function, even if
it works (which it does) what code in real-life contains this ?"

I am not thrashing you. I have academic exercises which theoretical to
the point of totally unrelated to the real world programming.  So, if
you think my ways of learning algorithms are not practical, you must
have something better to offer.

Your way of learing things is perfectly fine. I just responded to the
question:
"If I put Pirelli P Zero tires on my Volkswagen, how fast will it go?"
with the response:
"I wouldn't put Pirelli P Zero tires on a Volkswagen except in very,
very unusual circumstances."

How would you have answered the question?

If other regular posters say that Bubble-Sort is inherently bad idea
(except of the 2 cases you mention in an earlier reply) then I will
not use in the code I write for my employer. BTW, next algorithm in
Ullman's book is insertion sort

Insertion sort (and all other O(N*N) sorts are also bad except for
tiny partitions (though insertion sort on average is far better than
bubble sort except in very, very rare circumstances).

Insertion sort is useful as a finisher for small partitions. It is
typically used with quicksort or introspective sort in this fashion.
The idea is due to Richard Singleton (see ACM algorithm 347).

At any rate, consider another analogue:
"I want to enhance my Bobby Ayala baseball card. If I put it in a
solid gold, diamond-encrusted case with a transparent sapphire window,
how much will that increase the value?"
I suspect you might respond, "That treatment would be better spent on
your Babe Ruth rookie card."