Bubble Sort in C

[Phil Carmody]

I suppose there are practical physical uses for bubble sort, taking
advantage of its property that only adjacent elements are compared.

"If you're taller than the person on your right, swap places with
them."

You mean that if you *tell* people to engage in a step from bubble-
sort, they'll mimic part of the bubble-sort? You don't see anything
tautological about that?

Phil

 

[Phil Carmody]

Give a programming newbie a computer, however, and tell them to
write a sort routine, and they may well end up with bubble sort as
their first attempt.

I wouldn't expect that to be the common result unless the newbie had
already heard of bubble-sort.
Ditto.

The earliest program I can remember writing implemented an algorithm
which makes even bubble sort look good by comparison. It was written
in Fortran I, and I certainly don't have the text of that program any
more, but here's the same algorithm implemented in C99:

void sort_int(int array[], int n)
{
// I am quite certain my Fortran I version
// had nothing like the following statement:
if(array==NULL || n<2)
return;

for(int start=0; start < n - 1; start++)
{
int min = array[start];
int location = start;

// Find smallest element in rest of list
for(int next = start+1; next < n; next++)
if(array[next] < min)
{
min = array[next];
location = next;
}

if(location != start)
{ // Swap elements
int temp = array[start];
array[start] = array[location];
array[location] = temp;
}
}
}

That is an algorithm I could imagine a newbie inventing, but oddly
enough, that's not what actually happened - that's the algorithm our
teacher instructed us to implement.

More than three decades after the fact, I can't be sure, but I think
that if I'd been asked to choose my own sorting algorithm, I might
have come up with something like an insertion sort.

The above is the basis for what's known as the selection sort. It's
one of the two simpler-and-better-than-bubble-sort algorithms for
small datasets. Compare the number of swaps it does on arbitrary
data.

Phil

 

[Richard Tobin]

I suppose there are practical physical uses for bubble sort, taking
advantage of its property that only adjacent elements are compared.

"If you're taller than the person on your right, swap places with
them."

[/QUOTE]

You mean that if you *tell* people to engage in a step from bubble-
sort, they'll mimic part of the bubble-sort?

No, I mean that if you tell someone to sort a line of people into
height order, they might come up with bubble sort as a reasonable
way to do it.

You said that no-one would come up with bubble sort as a way to sort
cards, and you're right, it's not something you'd think of for that.
But there are different sorting situations where bubble sort might be
an intuitive choice.

-- Richard

 

[Keith Thompson]

No, I mean that if you tell someone to sort a line of people into
height order, they might come up with bubble sort as a reasonable
way to do it.

[...]

Particularly since, in that particular scenario, swapping two adjacent
elements is substantially cheaper than swapping two elements that are
far apart.

It would be interesting to analyze various sorting algorithms with the
assumption that moving items greater distances is more expensive.
(But it's not a C issue; probably comp.programming would be a good
place for it.)

 

[Phil Carmody]

probably quite efficient too. The swops will take place in parrallel

Nope. Even if you contrive a way for them to be done in parallel
(such as borrowing the first stage from a mergesort), then you'll
be performing the comparisons and swaps in a different order,
and thus won't be doing the bubble-sort any more. If you want to
parallelise something like a bubble-sort, then there's always the
shell-sort approach. (Which again, is no longer a bubble-sort.)
Merge-sort, as hinted at above, also has stages which can be performed
in parallel. (And again, isn't bubble-sort.)

Well-thought out parallelisation would of course permit sub-linear
sorting times, unlike your proposal which is O(n) in time and O(n^2)
in work. (Which is only useful if the data is self-modifying, and
needs to be sorted repeatedly, as just streaming the data into and
out of the grid is of course O(n). However, there are applications
which have that property in computational number theory, for example.)

Phil

 

[Nick Keighley]

Give a programming newbie a computer, however, and tell them to write
a sort routine, and they may well end up with bubble sort as their
first attempt.

I wouldn't expect that to be the common result unless the newbie had
already heard of bubble-sort.

The earliest program I can remember writing implemented an algorithm
which makes even bubble sort look good by comparison.
really?

It was written in
Fortran I, and I certainly don't have the text of that program any more,
but here's the same algorithm implemented in C99:

void sort_int(int array[], int n)
{
     // I am quite certain my Fortran I version
     // had nothing like the following statement:
     if(array==NULL || n<2)
         return;

     for(int start=0; start < n - 1; start++)
     {
         int min = array[start];
         int location = start;

         // Find smallest element in rest of list
         for(int next = start+1; next < n; next++)
             if(array[next] < min)
             {
                  min = array[next];
                  location = next;
             }

         if(location != start)
         {   // Swap elements
             int temp = array[start];
             array[start] = array[location];
             array[location] = temp;
         }
     }

}

That is an algorithm I could imagine a newbie inventing, but oddly
enough, that's not what actually happened - that's the algorithm our
teacher instructed us to implement.

More than three decades after the fact, I can't be sure, but I think
that if I'd been asked to choose my own sorting algorithm, I might have
come up with something like an insertion sort

isn't that algorithm insertion sort?

The worst sort I ever saw. The original was actually sorting letter-
digit
pairs (A1 F4 B1 J1 G2 C4 E3) but I've simplified it so it sorts
strings based on the first character.

void sort (char* sorted[], char* unsorted[], int n)
{
int i = 0;

for (letter = 'A'; i <= 'Z' && i < n; i++)
{
for (j = 0; j < n; j++)
{
if (unsorted [j][0] == letter)
{
sorted [i++] = unsorted [j];
break;
}
}
}
}

at worst it will take 26 passes to sort a maximum of 7 elements.
I didn't fix it because the arrays were so small.


--
my old favourite:


Quantum Boggum Sort:
Q1. use a source of quantum noise (eg. radioactive decay) to
randomly permutate an array.
Q2. if the array is not ordered, destroy the universe (*)
Q3. if you reached this step your universe has sorted the array
in O(n) time.

(*) [100] this is left as an exercise

 

[James Kuyper]

really?

Actually, no. Now that I've bothered to think about it more carefully, I
realize that the negative comparison I made, three decades ago, was to
quick sort, not bubble sort. It's an O(n^2) algorithm, like bubble sort,
but the coefficient of the n^2 term is smaller than for bubble sort.

It was written in
Fortran I, and I certainly don't have the text of that program any more,
but here's the same algorithm implemented in C99:

void sort_int(int array[], int n)
{
� � �// I am quite certain my Fortran I version
� � �// had nothing like the following statement:
� � �if(array==NULL || n<2)
� � � � �return;

� � �for(int start=0; start < n - 1; start++)
� � �{
� � � � �int min = array[start];
� � � � �int location = start;

� � � � �// Find smallest element in rest of list
� � � � �for(int next = start+1; next < n; next++)
� � � � � � �if(array[next] < min)
� � � � � � �{
� � � � � � � � � min = array[next];
� � � � � � � � � location = next;
� � � � � � �}

� � � � �if(location != start)
� � � � �{ � // Swap elements
� � � � � � �int temp = array[start];
� � � � � � �array[start] = array[location];
� � � � � � �array[location] = temp;
� � � � �}
� � �}

}

That is an algorithm I could imagine a newbie inventing, but oddly
enough, that's not what actually happened - that's the algorithm our
teacher instructed us to implement.

More than three decades after the fact, I can't be sure, but I think
that if I'd been asked to choose my own sorting algorithm, I might have
come up with something like an insertion sort

isn't that algorithm insertion sort?

No, as someone else has pointed out, it's a selection sort, as I would
probably known if I had been a CS major rather than a Physics major.
Before posting that message, I did a quick web search of the different
sorting algorithms, read a poorly worded description of selection sort,
and incorrectly concluded that it was something different. However,
Wikipedia's description matches the above algorithm perfectly.

 

[Nobody]

The worst sort I ever saw. The original was actually sorting letter-
digit
pairs (A1 F4 B1 J1 G2 C4 E3) but I've simplified it so it sorts
strings based on the first character.

void sort (char* sorted[], char* unsorted[], int n)
{
int i = 0;

for (letter = 'A'; i <= 'Z' && i < n; i++)
{
for (j = 0; j < n; j++)
{
if (unsorted [j][0] == letter)
{
sorted [i++] = unsorted [j];
break;
}
}
}
}

The outermost for loop is wrong; "letter" never changes. And the check
for i overflowing needs to be in the inner loop as well. IOW:

for (letter = 'A'; letter <= 'Z' && i < n; letter++)
{
for (j = 0; j < n && i < n; j++)

at worst it will take 26 passes to sort a maximum of 7 elements.
I didn't fix it because the arrays were so small.

That's basically a rather inefficient radix sort, with an unnecessary
constant factor of 26 thrown in. But, hey, it's O(n), so it's got to be
better than all of those slow O(n.log(n)) methods, right?

Question: how large would n need to be in order for the above to
actually outperform qsort()?

 

[David Thompson]

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

But the maximum displacement needed (for any inplace sort) and thus
the maximum passes needed for bubblesort is one less than the number
of data items, here the number of characters within the string.