PwnallthethingsFeb 16, 2023
Had to implement a sorting algorithm today for the first time in my entire career, so i guess finally learning about them decades ago paid off
Show threadPwnallthethings

Unfortunately since then, I've also learned about test-driven development, and forgotten everything I learned back then. So just went with

1. First implement a test routine "IsSorted(list)" to check the algorithm is right

Sort(list):
While(!IsSorted(list))
SwapRandomEntries(list);
return

Feb 16, 2023 at 3:46amWeb
Show threadPwnallthethingsFeb 16, 2023
Screw you computer science, computer go brrr.
Show threadPwnallthethingsFeb 16, 2023

Also fun fact, qsort() in your libc is likely only *sometimes* quicksort. And it's not quicksort based on a threshold that made sense for a Sun machine.

Anyway, in summary, lol computers

Show threadJared GreenoFeb 16, 2023
@Pwnallthethings i love that i once again have access to short form "lol computers" content.
Show threadDavidFeb 16, 2023

@Pwnallthethings how hard can sorting be anyway??

*checks notes* oh... oh no.

Show threadScott MichaudFeb 16, 2023
@docmagnificent @Pwnallthethings How hard can it be? Sort of.
Show threadJLab8Feb 16, 2023
@Pwnallthethings that's why I only ever work with custom standard library implementations that specifically target the hardware I'm building against.
Show threadCyrille CailacFeb 16, 2023
@Pwnallthethings meanwhile... https://www.phoronix.com/news/Intel-AVX-512-Quicksort-Numpy
Intel Publishes Blazing Fast AVX-512 Sorting Library, Numpy Switching To It For 10~17x Faster Sorts

Intel recently published an open-source C++ header file library for high performance SIMD-based sorting, which initially is focused on providing a lightning fast AVX-512 quicksort implementation

Show threadWillem JanssenFeb 16, 2023

@Pwnallthethings With some minor tweaks you can transform your algorithm into the best sort: Quantum Bogosort!

http://wiki.c2.com/?QuantumBogoSort

Show threadThomas A. Fine Feb 17, 2023

@Wlm @Pwnallthethings
In the infinite multiverse, each one of us lives forever in at least one universe.

So my mission is simply to destroy all the universes where I don't live forever.

Show threadWillem JanssenFeb 17, 2023
@thomasafine @Pwnallthethings So far so good!
Show threadSteve BellovinFeb 16, 2023
@Pwnallthethings The computational complexity of your solution is, umm, impressive…
Show threadPwnallthethingsFeb 16, 2023
@SteveBellovin but it works
Show threadSteve BellovinFeb 16, 2023
@Pwnallthethings And for reasonably small array sizes, it's not even too awful. Plus, you get your correctness test built-in. But for larger N—well, I wouldn't want to try that… (More seriously: as Kernighan has noted: first, get it right. Second, measure to find your real bottlenecks. Only then, optimize, and optimize in the right spots. In my formulation, there's no point to getting the wrong answer quickly.)
Show threadJohnMasheyFeb 16, 2023
@SteveBellovin @Pwnallthethings
And for *serious* sorting, Ordinal Technology's parallel nsort was already terrific in the 1990s on SGI multiprocessors (and others' as well):
2000 Paper by Ordinal's Chris Nyberg & Charles Koester & Microsoft's Jim Gray.
http://www.ordinal.com/NsortPara.pdf
Website: http://www.ordinal.com/
Show threadNicholas WeaverFeb 16, 2023
@SteveBellovin @Pwnallthethings
Relatedly, probably the most important concept we teach in the computer architecture class is Amdahl's law. "Only bother to optimize the bottlenecks", and programmer time matters too:
The runtime of your program is not just the runtime of your program, but the aggregate runtime of all invocations + the time it took you to write it in the first place.
Show threadPwnallthethingsFeb 16, 2023
@ncweaver @SteveBellovin 1000%. Which is why most libcs have weird aggressively hand-optimized memcpy routines, but qsort has stayed meh. Because qsort gets called almost never, and memcpy gets called so often in a normal run that even processor manufacturers come up with creative ways to do it faster.
Show threadCorey Rayburn YungFeb 16, 2023
@Pwnallthethings @SteveBellovin my high school computer science teacher used random sort as the baseline algorithm to compare other methods against it. Unfortunately for her, the first time she ran it, it beat all the other methods. Randomization is randomly better.
Show threadJames GarryFeb 16, 2023

@coreyrayburnyung @Pwnallthethings @SteveBellovin

And when quantum computing comes of age we'll just throw bits around randomly and rely on at least *one* reality getting it 'right'.

That'll be my excuse.

Show threadKris Sargent, MDFeb 16, 2023
@Pwnallthethings @SteveBellovin in the same sense as the monkeys, typewriters and the plays of Shakespeare... yes, it does.
Show threadWilliam HeroldFeb 16, 2023
@SteveBellovin @Pwnallthethings O(?)
Show threaddjmFeb 16, 2023
@willigula @SteveBellovin @Pwnallthethings O(My)
Show threadWilliam HeroldFeb 20, 2023
@djm @SteveBellovin @Pwnallthethings George Takei has entered the chat
Show threadpamsailsFeb 16, 2023
@Pwnallthethings So much of what I learned in CS classes (begin 1968) screamed in pain in real programming. The theory was nice, implementation met hardware. Retired now and brain is much happier playing the saxophone.
Show threadSteve LoughranFeb 17, 2023
@Pwnallthethings better hope the RNG works across the size of the list. Doesn't have to be evenly spread, just able to pick every element in the list
Show threadParker BenchleyFeb 17, 2023
@Pwnallthethings 43 years programming, 33 of them in the financial services industry, and on the rare occasion I have to sort an array, I still use a bubble sort. 🤷‍♂️
Show threadVance MaverickFeb 16, 2023
@Pwnallthethings it's not even guaranteed to terminate!
Show threadPwnallthethingsFeb 16, 2023
@vance_maverick but when it does, it's right
Show threadDavid BruchmannFeb 16, 2023
@Pwnallthethings @vance_maverick *IF* it does 😂
Show threadVance MaverickFeb 16, 2023
@davidbruchmann @Pwnallthethings right, you have to make assumptions about SwapRandomEntries to even demonstrate that the probability of termination converges on 1
Show threadneatcheeFeb 16, 2023
@Pwnallthethings perf optimization comes later
Show threadmjfgatesFeb 16, 2023
@Pwnallthethings Small set? It's fine. Just don't throw it at a million items :D
Show threadShailesh BavadekarFeb 16, 2023
@Pwnallthethings This only works if you first prove that IsSorted(list) works correctly. We must go deeper.
Show threadRobert MerkelFeb 16, 2023
@Pwnallthethings Bozosort!
Show threadAndrew Certain Feb 16, 2023
@Pwnallthethings A friend of mine was asked in his PhD quals about the runtime of sorting. He said the best algorithms were O(n log n), but other algorithms were "O (n^2) or worse." One of the examiners perked up and said, "can you give me an example of a sorting algorithm that is worse than O(n^2)?" My friend definitely panicked a bit, but then came up with the same one you did!
Show threadRobFeb 16, 2023
@Pwnallthethings 😹
Show threadisaacsFeb 16, 2023
@Pwnallthethings it's potentially O(1)!
Show threadRon HeywoodFeb 17, 2023
@Pwnallthethings https://blog.cleancoder.com/uncle-bob/2013/05/27/TransformationPriorityAndSorting.html
Clean Coder Blog