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 threadPwnallthethingsFeb 16, 2023

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

Show threadVance Maverick
@Pwnallthethings it's not even guaranteed to terminate!
Feb 16, 2023 at 3:48amWeb
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