5 ms·

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

rrdharan 3y ago
The “standard library” often isn’t available in early boot scenarios.
- pjmlp 3y ago
  True, but there are plenty of CS books about algoriths and data structures.
  - saagarjha 3y ago
    Converting those into code is not always trivial.
    - pjmlp 3y ago
      Depends on the quality of the degree. Besides I would assume anyone getting ready for their leetcode assignments goes through them anyway.
      - saagarjha 3y ago
        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.
  - naniwaduni 3y ago
    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.
    - pjmlp 3y ago
      Only if they never managed beyond first chapter.
      - deleted 3y ago
        [deleted]
    - anikan_vader 3y ago
      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 3y ago
        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.
    - tedunangst 3y ago
      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 3y ago
        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.
  - pengaru 3y ago
    Lifting sample code out of an academic text, now there's a winning strategy for rock solid stability, correctness, and performance!
    - pjmlp 3y ago
      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.
- thomastjeffery 3y ago
  The standard library can be statically linked...
  - xorvoid 3y ago
    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 3y ago
      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.
toast0 3y ago
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 3y ago
  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 3y ago

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

pjmlp 3y ago
True, but there are plenty of CS books about algoriths and data structures.
- saagarjha 3y ago
  Converting those into code is not always trivial.
  - pjmlp 3y ago
    Depends on the quality of the degree. Besides I would assume anyone getting ready for their leetcode assignments goes through them anyway.
    - saagarjha 3y ago
      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.
- naniwaduni 3y ago
  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.
  - pjmlp 3y ago
    Only if they never managed beyond first chapter.
    - deleted 3y ago
      [deleted]
  - anikan_vader 3y ago
    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 3y ago
      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.
  - tedunangst 3y ago
    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 3y ago
      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.
- pengaru 3y ago
  Lifting sample code out of an academic text, now there's a winning strategy for rock solid stability, correctness, and performance!
  - pjmlp 3y ago
    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.
thomastjeffery 3y ago
The standard library can be statically linked...
- xorvoid 3y ago
  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 3y ago
    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.

toast0 3y ago

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 3y ago
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.