[dheera]

Probably because it's MUCH easier to code bubblesort without making mistakes that cause it to not terminate or some such. Especially if they are writing the bootloader in assembly.

For something mission critical like a bootloader that's more valuable than turning O(n^2) into O(n log n). People running systems like BSD largely don't care how long the system takes to boot, once it's booted the system runs for years.

[naniwaduni]

The funny thing is that, in my experience, bubble sort is actually pretty hard to write, because the finicky details of the swap step don't make sense (in a "wait, this can't possibly be right, there's no way you'd want to write it like that" kind of way). Better than even odds that if you have someone write a "bubble sort" without reference, you get an accidentally insertion sort variant.

[dmitrygr]

The easiest sort to implement in assembly is probably selection sort. Bubble sort is actually messier :)

Source: written sorts in assembly more times than I would care to count.

[tinus_hn]

You shouldn’t write a sort algorithm because much smarter people have already done so and their work is included in the standard library.

[toast0]

Sure. In this case, the smarter people wrote the sort in ~1995 and it was good enough for nearly 30 years, but now someone has to step up and be smart again.

You can't always rely on smarter people to be there to do things for you. And you also can't rely on the standard library to have been written by smarter people anyway, and even if so, to have been written by smarter people in order to handle the situation you find yourself in. There's lots of ways to sort, and lots of good reasons to choose ways that are less than optimal for the use cases they end up being used in.

[tinus_hn]

You’re defending the claim that implementing qsort is too hard, definitely the people who wrote the standard library are smarter than the people putting in bubble sort because quicksort is too hard.

This is just a moronic defense of the venerated FreeBSD developers, it’s on a level equal to organized religion. The FreeBSD developers are fine developers and this was dumb, that’s why they replaced it.

And in this day and age there really is no argument for any user space c environment to exist where the qsort standard library function is not available. And even if there was, it would still be smarter to just copy and paste the battletested code from the c library than write another implementation. Because that’s how you end up with bubblesort because doing it right is too hard.

[rrdharan]

The “standard library” often isn’t available in early boot scenarios.

[pjmlp]

True, but there are plenty of CS books about algoriths and data structures.

[naniwaduni]

Copying a convenient-looking one out of a CS book is how you end up with a bubble sort. Approximately nobody comes up with a bubble sort from scratch; it's obviously, gratuitously bad in a way that there's no practical reason to think of on your own. The sorts that people come up with without reference are usually insertion and selection sorts—those two were discovered before bubble sort.

[tedunangst]

Bubble sort occupies a weird space where people assume it's dumb and simple so it'll be the least code, but even insertion sort tends to beat it.

[naniwaduni]

I mean yeah, bubble sort is basically insertion sort but weirdly pessimized in a way that makes negative sense. Giving it a catchy name has probably been a net harm.

[anikan_vader]

Plenty of children come up with bubble sort as a sorting algorithm. It’s intuitive to go down the list swapping any pairs that happen to be in the wrong order.

[naniwaduni]

It's also very intuitive to pick out a misplaced item and put it in the right position. In the context of physical objects (e.g. playing cards), it's even more intuitive to come up with a (two-way) insertion sort than a bubble sort.

[pjmlp]

Only if they never managed beyond first chapter.

[pengaru]

Lifting sample code out of an academic text, now there's a winning strategy for rock solid stability, correctness, and performance!

[pjmlp]

It is at least on the world where being an engineer actually requires a degree, and not just because someone likes the word.

The real ones, the ones that write USENIX papers.

[saagarjha]

Converting those into code is not always trivial.

[pjmlp]

Depends on the quality of the degree.

Besides I would assume anyone getting ready for their leetcode assignments goes through them anyway.

[saagarjha]

Nah, it’s not. Correctly implementing algorithms is hard; it’s easy to create incorrect behavior on edge cases and performance pitfalls. I’m sure you knew about the Java issue from a while back, for example.

[thomastjeffery]

The standard library can be statically linked...

[xorvoid]

People who think this way haven’t written boot code.. I suppose you’re gonna link the c runtime too and it’s assumption of being a “process” under some “operating system”.. oh wait.

Compared to the rest of the task, writing a sort is pretty darn trivial.

[tedunangst]

This is true if we're talking about the first stage bios boot that needs to fit in 512 bytes, but there aren't any particular restraints on kernel size at the point in question. Link in anything you want, including qsort.