News for hackers. Stuff that matters.

A comment on O(n^2), again, now in Windows Management Instrumentation. Parent comment

Re:O(n^2), again, now in Windows Management Instrumentation by ynik on Monday December 09, 2019 @05:37PM (#21747419)
Bubble sort is popular because it's provably optimal... under extremely restrictive circumstances: https://stackoverflow.com/a/3274203 Those circumstances stopped being semi-relevant when even the cheapest computers started using (floppy) disk drives instead of tape drives, but somehow bubble sort is still being taught.
[ Parent | on HN ]
Re:O(n^2), again, now in Windows Management Instrumentation by NeoBasilisk on Monday December 09, 2019 @05:49PM (#21747512)
It's probably because the implementation of the algorithm is the simplest, because you don't need to modify the existing data structure. You don't need to merge or create new arrays. You just repeatedly loop and swap two elements when needed. Super easy by all metrics.
[ Parent | on HN ]
Re:O(n^2), again, now in Windows Management Instrumentation by vengefulduck on Monday December 09, 2019 @08:08PM (#21748627)
You don’t need to modify the data structure for most quadratic sorts though. Or even for quick sort.
[ Parent | on HN ]
Re:O(n^2), again, now in Windows Management Instrumentation by BubRoss on Tuesday December 10, 2019 @07:29AM (#21751812)
Most people get the partition algorithm wrong on their first try if they write it themselves.
[ Parent | on HN ]