7 ms·
American flag sort
- muti 2y agoVisualisation https://www.youtube.com/watch?v=k1XkZ5ANO64 https://www.youtube.com/watch?v=k1XkZ5ANO64 Wikipedia page https://en.wikipedia.org/wiki/American_flag_sort https://en.wikipedia.org/wiki/American_flag_sort
- AnarchismIsCool 2y agoLooks more like anarchist flag sort...
- codetrotter 2y agoI’ll take your word for it, AnarchismIsCool ;)
- aaron695 2y ago> Visualisation https://www.youtube.com/watch?v=k1XkZ5ANO64 https://www.youtube.com/watch?v=k1XkZ5ANO64 OT: I quite liked the follow up video Youtube suggested - Sorting algorithms to relax/study to - https://www.youtube.com/watch?v=vr5dCRHAgb0 https://www.youtube.com/watch?v=vr5dCRHAgb0
- peterleiser 2y agoThe next video that came up for me was "sorting algorithms to relax/study to": https://www.youtube.com/watch?v=vr5dCRHAgb0 https://www.youtube.com/watch?v=vr5dCRHAgb0 I'm almost embarrassed by how long I've watched it!
- knodi123 2y agoNo offense, but I don't think that visualization helps very much. Here's a visualization of a much larger data set that illustrates what's actually happening with the buckets and the major steps. https://www.youtube.com/watch?v=21jEd1FUiV8 https://www.youtube.com/watch?v=21jEd1FUiV8
- fourteenfour 2y agoThanks, this one makes the stripe pattern much more apparent.
- deleted 2y ago[deleted]
- tomphoolery 2y agoFreedom Sort.
- tantalor 2y agoFor democracy!
- seattle_spring 2y agoI'm doing my part!
- __d 2y agowould you like to know more?
- tomschlick 2y agoCue the Team America theme song
- mcfedr 2y agoThat is basically what I hear in my head everytime I see that flag
- tom_ 2y agoIf you disagree, see the first amendment! If you still disagree, see the second amendment!
- mondobe 2y agoAnd if you STILL disagree, see the third amendment! If you're a soldier, in my house, I guess.
- deleted 2y ago[deleted]
- deleted 2y ago[deleted]
- karmakaze 2y agoAt first I didn't think I'd be interested. > Using some efficiency techniques, it is twice as fast as quicksort for large sets of strings.
- hinkley 2y agoI’m not calling it flag sort. It’s an in-place bucket sort which is interesting.
- wodenokoto 2y agoFrom Wikipedia[1]: > The name American flag sort comes by analogy with the Dutch national flag problem[2] in the last step: efficiently partition the array into many "stripes". [1] https://en.m.wikipedia.org/wiki/American_flag_sort https://en.m.wikipedia.org/wiki/American_flag_sort [2] https://en.m.wikipedia.org/wiki/Dutch_national_flag_problem https://en.m.wikipedia.org/wiki/Dutch_national_flag_problem
- remram 2y agoOr in-place radix sort maybe. I agree with you, the name is ridiculous, reminds me of miracle sort or intelligent design sort: https://www.dangermouse.net/esoteric/intelligentdesignsort.html https://www.dangermouse.net/esoteric/intelligentdesignsort.h... Probably those two flag sort algorithms were named before the joke algorithms were popularily known.
- thefifthsetpin 2y agoQuicksort isn't great when comparing two items is expensive.
- owlninja 2y agoThe 'more information' site linked on the page seems like something some HN folk love. https://www.workmall.com/flags/united_states_flag.html https://www.workmall.com/flags/united_states_flag.html
- defrost 2y agoThere's a Peter M. McIlroy as well!?! All this time and I thought it was just Doug, I'm guessing Peter might be the son of the father of pipe?
- icsa 2y agoYes. He is a software engineer in Seattle.
- deleted 2y ago[deleted]
- jdeisenberg 2y agoWondering how this sort would perform with Unicode input (given 256 buckets); specifically what the results would look like.
- bawolff 2y agoPresumably it would be fine, since unicode input is still a string of bytes at the end of the day.
- nanidin 2y agoIt says it sorts one byte at a time. I think this would break for anything not utf-8.
- ts4z 2y agoSeems like it should work for arbitrary byte strings (any charset, any encoding)but obviously the performance characteristics will differ because of non-uniform distribution. But that happens even in ASCII.
- nanidin 2y agoYes, you’ll get something sorted based on the bytes in the string but it won’t be lexicographically correct - for example, à will be sorted after b.
- brirec 2y agoThis would even break UTF-8, since multi-byte characters are a thing!
- dumbo-octopus 2y agoHow would that break anything? The strings aren't being split.
- EmilyHughes 2y ago
- re 2y agoLooks like there's a Rust implementation: https://crates.io/crates/afsort https://crates.io/crates/afsort > When sorting English words, this implementation seems to be about 40% faster than sort_unstable from the Rust standard library. That's better than I would have expected. It would be interesting to see how it does on other types of string sort problems.
- antonhag 2y agoHi! Crate author here, happy to see my old project getting mentioned. Let me know if you have any questions!
- ewalk153 2y agoDo you actively use this function in any projects? What was your inspiration to write the crate?
- antonhag 2y agoI don't actively use it, unfortunately. The main inspiration was to faster sort inputs into the https://github.com/BurntSushi/fst https://github.com/BurntSushi/fst crate, which I in turn used to try to build a search library.
- Zelizz 2y agoPretty much just a variation of counting sort with a worse name? https://en.wikipedia.org/wiki/Counting_sort https://en.wikipedia.org/wiki/Counting_sort
- carabiner 2y agoA superior name.
- dumbo-octopus 2y agoNo. The very article you link details the difference, and that Counting Sort is often a subroutine in Radix Sort, and that Counting Sort is extremely poorly suited to strings, which is the entire purpose of this sort. And this name is better. So... "no" in basically every way possible.
- Zelizz 2y agoCharacters in a string can be thought of as digits in a base-256 number. Call counting sort recursively on each bucket, looking at the next character in the string. Can you not see the similarity?
- chowells 2y agoThere is no one who fails to see the similarity, because they're both kinds of radix sorts. For instance, a counting sort is a degenerate form of radix sort that only does one pass. But where the classic radix sort is bottom-up, the American flag sort is top-down. That really matters for data where the the most significant portions of the data is likely to be all you need to consider for the sorting. While a top-down sort will have similar performance to bottom-up in the worst case, in the best case it can skip a lot of passes, especially if the inputs are much longer than the longest common prefix.
- dumbo-octopus 2y agoThey're related, but in a very specific way that does not meet the bar for "variation" in my opinion. As you described, counting sort is a very simple procedure that works well only on a very specific input domain. If another algorithm has "more logic" than counting sort itself in order to transform a very different input domain into a format that is suited for making many repeated calls to (a procedure that may be implemented as) counting sort, in a specific pattern, and appropriately coalescing the results of those calls, I think it is appropriate to let it have its own name. Would you prefer to refer to every possible utilization of counting as "that version of counting sort where...."?
- Someone 2y agoThe paper (https://static.usenix.org/publications/compsystems/1993/win_mcilroy.pdf https://static.usenix.org/publications/compsystems/1993/win_...; linked to from the page) is well-written and worth reading, iterating over multiple C programs that build up to this sort algorithm and giving a good rationale for each iteration.
- awanderingmind 2y agoThere is currently a typo in the link which prevents it from working - the correct link is https://static.usenix.org/publications/compsystems/1993/win_mcilroy.pdf https://static.usenix.org/publications/compsystems/1993/win_... Interesting read, thanks!
- Traubenfuchs 2y ago> it is twice as fast as quicksort for large sets of string Define large.
- throwaway984393 2y ago[dead]
- TheRealPomax 2y agoThey did. But you'll need to read the (free) paper [1] to get the details omitted in the NITS catalog summary. [1] http://www.usenix.org/publications/compsystems/1993/win_mcilroy.pdf http://www.usenix.org/publications/compsystems/1993/win_mcil...
- Oarch 2y agoThe comments made me realise there's no national flag with lots of vertical stripes. Seems like a hole in the market. Someone alert CGP Grey!
- deleted 2y ago[deleted]
- Kon-Peki 2y agoSorts like these work really well on GPUs. You would start with a single thread for the first pass and then keep spawning one-thread-per-bucket for every additional pass until done. It isn't particularly taxing on the GPU; your advantage comes from being able to run potentially thousands of threads simultaneously without having to worry about coordinating read/write memory access.
- NikkiA 2y agoThis strikes me that it should parallelize pretty well if you deputise the individual stripes to multiple threads.
- franze 2y agotoday i coded franzSort, faster than mergeSort, slower than quickSort function franzSort(a) { function m(l, r) { let s = []; while (l.length && r.length) { if (l[0] <= r[0]) { s.push(l.shift()); } else { s.push(r.shift()); } } return s.concat(l).concat(r); } if (a.length <= 1) { return a; } let h = Math.floor(a.length / 2); return m(franzSort(a.slice(0, h)), franzSort(a.slice(h))); } // Example usage let arr = [5, 3, 8, 6, 2, 7, 1, 4]; let sortedArr = franzSort(arr); console.log(sortedArr);
- jon_richards 2y agoThe stars in the American flag aren't used. This is clearly Pride flag sort.
- oniony 2y agoAnd Mauritius's flag has more stripes.