On Wed, 18 Mar 2026 11:20:03 +0100
David Brown <david.brown@hesbynett.no> wrote:
I think this needs to start from 0.The language is 'C'.The problem with bubble sort is that relatively to other popular>
O(n**2) sorting algorithms, i.e. using Knuth's nomenclature,
Straight Insertion and Straight Selection, it is not just
measurably slower, but also a little more complicated to code.
I am not convinced on the complexity point - but it will vary by
programming language, and what you consider "complicated".
>
Here are implementations of Straight Insertion and Straight Select.
Show me implementation of Bubble sort that is not at least a little
more complicated.
Remember that it has to be "real" bubble sort, not a simplified bubble
sort that does unnecessary work by starting each time from the
beginning. Your variant shall avoid obviously unnecessary work and
shall be opportunistic, i.e. quick at handling almost sorted cases.
#include <stddef.h>
#include <string.h>
void straight_insertion_sort(const char** buffer, size_t n)
{
for (size_t i = 1; i < n; ++i) {
const char* a = buffer[i];
size_t k;
for (k = i; k != 0; --k) {
if (!(strcmp(a, buffer[k-1]) < 0))
break;
buffer[k] = buffer[k-1];
}
buffer[k] = a;
}
}
void straight_select_sort(const char** buffer, size_t n)
{
for (size_t i = 1; i < n; ++i) {
const char* mn = buffer[i];I ported both of these to scripting code, then compared against the simplest version of bubble-sort.
size_t mn_k = i;
for (size_t k = i+1; k < n; ++k) {
if (strcmp(buffer[k], mn) < 0) {
mn = buffer[k];
mn_k = k;
}
}
buffer[mn_k] = buffer[i];
buffer[i] = mn;
}
}
They were faster, by 2.7x and 3.6x respectively. But both still had O(n-squared) behaviour.
Now that I have copies, I may possible use them next time I might have written a bubble-sort. But I would only have done that anyway when I knew its performance was tolerable or negligible.
Normally however (and again in scripting code) I'd use my built-in sort() based on quicksort, which is nearly 1000 times faster than bubble-sort for my test (sort 20K random strings), and some 300x faster than your routines. It's not O(n-squared) either.
So basically, if I don't care about speed or its not needed, I might as well use bubble-sort.
Les messages affichés proviennent d'usenet.