4 ms·
Each time a discussion about sorting starts, I'm reminded of a "lively debate" I had with my boss/friend about the most optimal sorting approach. He claimed it'
by vprcic 8mo ago
Each time a discussion about sorting starts, I'm reminded of a "lively debate" I had with my boss/friend about the most optimal sorting approach. He claimed it's O(n) pointing to counting sort as an example. This didn't sit well with me. A sorting algorithm, I insisted, should be defined something like "a function taking an unsorted array of elements and returning a sorted one". But it seems there is no agreed upon definition and you can have something like counting sort where you get an array in O(n) but still need O(m) to get the index of a specific element. I argued that then the best sorting algorithm is the do-nothing algorithm. It returns the initial array in O(1), but needd O(m log m) to get you the index of an element (it uses merge sort to do it).
- tpoacher 8mo agoYou reminded me of "Sleep Sort" [0] [0] https://news.ycombinator.com/item?id=2657277 https://news.ycombinator.com/item?id=2657277
- NooneAtAll3 8mo agocounting sort is O(nW), where W is largest value if you don't care about W or it is essentially constant - then it can be dropped but it is an input parameter that will change execution time
- emil-lp 8mo agoW is the span or range.
- marcosdumay 8mo agoIt's O(n+W), not O(n*W). > if you don't care about W or it is essentially constant - then it can be dropped Also, every algorithm that ends in a real computer is bound to a constant time. That's still not a practical thing to do.
- vlovich123 8mo agoThe simplification is correct but not correctly stated (even though colloquially it's common to state it that way). Technically it's when some component of the algorithm is dwarfed by another, then you can exclude it (i.e. O(n+W) =~ O(n) when W <<< n, O(mn) =~ O(n) when m <<< n etc). It's colloquially shortened to "when it's a constant" because generally it's constant regardless of program execution whereas the variable parts of the formula actually do change and thus the big-O analysis does still give you a correct lower bound on the performance. TLDR: You're being unhelpfully pedantic.
- myhf 8mo ago"ordering" means arranging things in order by some metric. "sorting" means assigning things into bins (which are usually ordered).
- emil-lp 8mo agoThis is news to me. Source?
- thom 8mo agoWhat do you do when you sort your washing?
- nh23423fefe 8mo ago"The children were sorted in to two lines by gender then ordered by height" You might substitute "sorted by height" but its certainly not a correction. While "ordered into lines" would be an error.
- ninalanyon 8mo agoThe sorting office for a postal service.
- michaelt 8mo agoThat's because it's not true. https://www.merriam-webster.com/dictionary/ordering https://www.merriam-webster.com/dictionary/ordering Order - transitive verb - 1. to put in order : arrange - "The books are ordered alphabetically by author." noun - 4. b(1) the arrangement, organization, or sequence of objects or of events - "alphabetical/chronological/historical order" "listed the items in order of importance" https://www.merriam-webster.com/dictionary/sorting https://www.merriam-webster.com/dictionary/sorting Sort - transitive verb - 1. to put in a certain place or rank according to characteristics - "sort the mail" "sorted the winners from the losers" "sorting the data alphabetically" noun - 5. an instance of sorting - "a numeric sort of a data file"
- rkomorn 8mo agoI don't get how this disagrees with what GGP wrote.
- hinkley 8mo agoI can’t think of a single time I’ve needed a sorted list of only numbers. It’s always numbers and something else, like names or dates. Maybe for median calculations, but I don’t even use those that much either. Especially in telemetry, where mean is easy and median is not.
- pvillano 8mo agoTo be pedantic, median is cheaper than sorting. O(n) with a quicksort-like algorithm. Also, if you're taking an average of floating point numbers, you might want to sort it first and add from smallest to largest, to better preserve precision
- lscharen 8mo agoAn aside, but I recently learned -- if one is willing to use a very modest amount of memory -- summing floating-point numbers with no loss of precision is effectively a solved problem with the XSUM algorithm. https://glizen.com/radfordneal/ftp/xsum.pdf https://glizen.com/radfordneal/ftp/xsum.pdf
- tialaramex 8mo agoThat paper explains some useful optimisation details, but obviously since the floats are all (either infinity or) some multiple of a known tiny fraction (their smallest non-zero number), we can definitely sum them accurately.
- mjcohen 8mo agoNot if the ratio between the largest and smallest floats is very large (2^(2^n)) where n is the number of bits in the exponent.
- tialaramex 8mo agoI think you either haven't thought about this or you did your math wrong. You need (2^e)+m+1 bits. That is more bits than would fit in the cheap machine integer type you just have lying around, but it's not that many in real terms. Let's do a tiny one to see though first, the "half-precision" or f16 type, 5 bits of exponent, 10 bits of fraction, 1 sign bit. We need 43 bits. This will actually fit in the 64-bit signed integer type on a modern CPU. Now lets try f64, the big daddy, 11 exponent, 52 fraction, 1 sign bit so total 2048 + 52 + 1 = 2101 bits. As I said it doesn't fit in our machine integer types but it's much smaller than a kilobyte of RAM. Edited: I can't count, though it doesn't make a huge difference.
- Epa095 8mo agoUsually when one talk about sorting, without specifying closer, one means comparison sort [1], which indeed has an average-case lower bound of O(n*log(n)). In more special cases all kinds of other runtimes are possible. 1: https://en.wikipedia.org/wiki/Comparison_sort https://en.wikipedia.org/wiki/Comparison_sort
- jalacira 8mo ago[dead]
- deleted 8mo ago[deleted]
- onecommentman 8mo agoObligatory mention of the linear time analog sorting algorithm known as the “spaghetti algorithm”. https://en.wikipedia.org/wiki/Spaghetti_sort https://en.wikipedia.org/wiki/Spaghetti_sort https://every-algorithm.github.io/2023/11/25/spaghetti_sort.html https://every-algorithm.github.io/2023/11/25/spaghetti_sort.... The equivalent for positive link weight shortest paths is the “string algorithm” — build the network out of string and pull taut between the two knots/nodes, the resulting set of taut links is the shortest path.