9 ms·
Is this the simplest (and most surprising) sorting algorithm ever? (2021)
- berbec 2y agoAlgorithm 1 ICan’tBelieveItCanSort(A[1..n]) for i = 1 to n do for j = 1 to n do if A[i] < A[j] then swap A[i] and A[j]
- dang 2y agoFor code formatting, you can prepend two spaces to a line (this is in https://news.ycombinator.com/formatdoc https://news.ycombinator.com/formatdoc). (That's what ColinWright did at https://news.ycombinator.com/item?id=43162234 https://news.ycombinator.com/item?id=43162234 for example.)
- tromp 2y agoPrevious discussion: https://news.ycombinator.com/item?id=28758106 https://news.ycombinator.com/item?id=28758106
- dang 2y agoThanks! Macroexpanded: Is this the simplest (and most surprising) sorting algorithm? - https://news.ycombinator.com/item?id=28758106 https://news.ycombinator.com/item?id=28758106 - Oct 2021 (318 comments)
- ColinWright 2y agoFormatted: For easier exposition in the proof later on, the array is 1-based, so the elements are A[1]...A[n]. Algorithm 1 ICan’tBelieveItCanSort(A[1..n]) for i = 1 to n do for j = 1 to n do if A[i] < A[j] then swap A[i] and A[j]
- AnimalMuppet 2y agoIsn't that just BubbleSort? And, if so: they're writing Arxiv papers on BubbleSort now?
- sorokod 2y agoNote the: A[i] < A[j]
- casey2 2y agoYou can use 1..n+1 for both indices to get a sorted array with >
- skeaker 2y agoNo.
- GuB-42 2y agoIt is not, it is actually closer to an insertion sort. The interesting part is that it often comes up when the one writing the algorithm doesn't know what he is doing, and yet, it works. It may look like a BubbleSort because it is a common wrong implementation of BubbleSort. EDIT: insertion, not selection
- capitainenemo 2y agoYeah, section 3.2 of the PDF, titled '"Improving" the algorithm' notes that they have "rediscovered" insertion sort by simply adjusting the loop indices. (they also document a variant in 3.1 with similar indices tweaking which they describe as similar to an exchange sort)
- deepspace 2y agoYou did not bother to read the article, did you?
- codr7 2y agoBubbleSort keeps going until no more swaps happen, this algorithm specifies up front which items to compare. I actually think it's pretty cool, it happens occasionally that I just need a quick and dirty sort and this is easier to get right.
- tasty_freeze 2y agoThis isn't surprising to me in the least that it works. In the first pass (i=1), A[1] will end up with the largest value and a later pass cannot displace it. In the second pass (i=2), A[2] will end up with the 2nd largest value (which might be the same as the largest value, if it appeared more than once in the list). And so on.
- ColinWright 2y agoYou would appear to be wrong, because A[1] ends up with the smallest element. Specifically, on each case when i=2 and higher, j will still start at 1, so A[1] will still get referenced.
- jmholla 2y agoOn the first pass, A[1] ends up the largest element. On subsequent passes, it ends up with the smallest element in A[1:i].
- bmacho 2y ago> In the first pass (i=1), A[1] will end up with the largest value and a later pass cannot displace it. Nah, it will get displaced later. Notice that in the inner loop j goes from 1, and not from i. After i=1 A[1] will be the largest element, but after the next big step, after i=2, A[2] will be the largest element. (And after i=n, A[n] will be the largest element, as expected.) > In the second pass (i=2), A[2] will end up with the 2nd largest value The algorithm sorts the array ascending, and not descending. There is an example run linked in a grandkid comment, by jmholla. (This comment was entirely rewritten.)
- y-curious 2y agoFeels oddly familiar; I'm pretty sure this was the optimal solution to a leetcode problem (with specific constraints) that I saw during interview practice. Coming up with this on the fly during an interview would have been extra impressive.
- phkahler 2y agoQuestion on paper writing... There is only one author listed, but the wording keeps using "we" as in "we show that..." Is it considered poor practice to use "I" in a one-person paper? Or is "we" including the reader in the exposition?
- bglazer 2y agoThe “royal we” is common for single author academic work. I’m honestly unsure why. StackExchange seems to think it refers to both author and reader together. I think it conveys a sort of distance from the author, giving the writing less of a personal and more general tone. https://hsm.stackexchange.com/questions/2002/how-did-royal-we-become-a-standard-of-scientific-writing https://hsm.stackexchange.com/questions/2002/how-did-royal-w...
- NotAnOtter 2y agoIt's assumed you at some point talked to someone in the lab, or your advisor, or your advisee, or literally anyone about the paper. If you didn't that's probably problematic. So "we" gives non-formal credit to your community.
- tgv 2y agoI have never heard that as an explanation. That kind of credit is often expressed in foot/end notes, at least in the field I worked in. It is implied that the authors speak for themselves.
- NotAnOtter 2y agoWell IMO if you're giving some trivial level of credit someone else, you should use 'we', since you're both 'talking. If you reference them by name in the paper somewhere, I feel even stronger about my stance.
- noqc 2y agoWhen I use it, I mean it the way stackexchange says it is meant
- javierlc 2y agoThis is well known (google trivial sorting network!), and it would never be published anywhere peer-reviewed. Good reminder that Arxiv is not peer-reviewed :/
- justinpombrio 2y agoI did search for "trivial sorting network", but the only networks that were called trivial were the ones for exactly two elements, while this algorithm sorts an arbitrary number of elements. Could you link to what you're talking about? And what's its big-O runtime?
- javierlc 2y agoThere is discussion about Sorting Networks in the old post (find link in one of the top comments of this post)
- javierlc 2y agoThis is a much stronger result from the 80s: https://www.researchgate.net/publication/221590321_An_On_log_n_Sorting_Network https://www.researchgate.net/publication/221590321_An_On_log...
- deleted 2y ago[deleted]
- jancsika 2y agoOoh, I could copy A to B and add a final two lines: "else swap B[i] and B[j]" And now it's constant time!
- reedf1 2y agoThis is a sort I use all the time. Especially in coding challenges (AoC) because I'm usually lazy. It's nice to see it formally evaluated, it feels very intuitive to me.
- ColinWright 2y agoThis intrigues me. Would you be willing ... without looking at this article ... to provide exactly the code you "use all the time"? I'd like to compare what you write with the code in the article, because code that I write as a quick and dirty sort is definitely not this. In particular, this seems to take items that are already the right way round, and swaps them. I definitely don't do that. To be specific, I just knocked this out: #!/usr/bin/python a = [ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9 ] N = len(a) for i in range(0,N-2): for j in range(i+1,N-1): if a[i]>a[j]: a[i],a[j] = a[j],a[i] print a Specifically, note that I ask if a[i] is bigger than a[j] and if so then I swap them. The code in the article appears to do exactly the wrong thing, and I'd be surprised if your "go to" code does it the same way as the code in the article.
- reedf1 2y agoSure I have a "live" example in my 2024 AoC code. I'll add it here when I get home.
- ColinWright 2y agoFabulous ... thanks. I've bookmarked this bit of the thread so I can come back and check it. Cheers!
- reedf1 2y agoHi - for https://adventofcode.com/2024/day/5 https://adventofcode.com/2024/day/5 (Part 2): instructions = [] updates = [] with open("input.txt") as file: for line in file: line = line.rstrip() if line == "": break x, y = line.split('|') instructions.append((int(x), int(y))) for line in file: line = line.rstrip() pages = [int(i) for i in line.split(',')] updates.append(pages) def is_valid_update(update, instructions): pos = {num: idx for idx, num in enumerate(update)} for x, y in instructions: if x in pos and y in pos and pos[x] > pos[y]: return False return True valid_updates = [upd for upd in updates if is_valid_update(upd, instructions)] accum_valid = sum(upd[len(upd) // 2] for upd in valid_updates) print("Sum from valid updates:", accum_valid) def domain_sort(update, instructions): n = len(update) for i in range(n): for j in range(n): if (update[j], update[i]) in instructions: update[i], update[j] = update[j], update[i] return update invalid_updates = [upd for upd in updates if not is_valid_update(upd, instructions)] sorted_updates = [domain_sort(upd.copy(), instructions) for upd in invalid_updates] print("Sorted invalid updates:") for upd in sorted_updates: print(upd) accum_sorted = sum(upd[len(upd) // 2] for upd in sorted_updates) print("Sum from sorted invalid updates:", accum_sorted)
- NotAnOtter 2y agoThis isn't even worthy of a blog post let alone a published research article, the publisher should be embarrassed. This isn't an innovation. It's just un-optimized bubble sort. Back in college when I was learning bubble sort, I implemented this exact sort as a type of "MVP". And then I added the other flags and stuff they reference to try to polish the turd. I mean I'm glad someone proved it works, but I thought they proved this works like 40 years ago.
- strangattractor 2y agoWorst case bubble sort is n^2 - this one is n^2 for all cases even an already sorted list.
- NotAnOtter 2y ago...Right.. unoptimized bubble sort.
- ColinWright 2y agoOn any bubble sort, optimised or not, no swaps are made on an array that's already sorted. The routine in the article does. So no, it's not a bubble sort, unoptimised or otherwise. If you think it is a bubble sort then I'd be interested in seeing your implementation of a bubble sort, and an explanation as to why they are effectively the same.
- deleted 2y ago[deleted]
- SkiFire13 2y agoI can't see how this looks like a bubble sort to you, the inner loop isn't even comparing adjacent elements of the array. Moreover the comparison is the opposite of what you would normally do: if A[i] < A[j] then swap(A[i], A[j])
- LiamPowell 2y agoSee also: I can’t believe that I can prove that it can sort - https://news.ycombinator.com/item?id=31975507 https://news.ycombinator.com/item?id=31975507 - Jul 2022 (115 comments) Here's some other sorting algorithms proven with SPARK, with much more straightforward proofs: https://github.com/AdaCore/spark2014/blob/master/testsuite/gnatprove/tests/281__sorts/main.adb https://github.com/AdaCore/spark2014/blob/master/testsuite/g...
- jounker 2y agoIs this a joke paper? This is unoptimized bubble sort. This is the first sort I wrote when I was 13. This is literally the most obvious sort that exists.
- NotAnOtter 2y agoRight there with you.
- Y_Y 2y agoIs this a joke comment? It's not a bubble sort. The article explains.
- seanalltogether 2y agoIf you want to test it for yourself https://jsfiddle.net/px2jvzyn/ https://jsfiddle.net/px2jvzyn/
- ColinWright 2y agoLots of people in this thread saying that it's just an unoptimised Bubble Sort. No, it really isn't. In bubble sort you see if two things are the wrong way round and it they are then you swap them. This does that (sort of) the "wrong way round". In Bubble Sort your indices are always i<j ... here they aren't. In Bubble Sort you only ever compare adjacent items. Here you don't. This really, really isn't Bubble Sort, unoptimised or other. Also, with Bubble Sort it's really easy to prove that it works. If you think this is "just unoptimised Bubble Sort" then I'd be interested to see your proof that this algorithm works. So my feeling is that when people are dismissive of this, either they've not understood this at all, or they've understood it at a really, really deep level that I haven't. In that latter case I'd really appreciate a better explanation for what you think is going on, and why you think this is "just an unoptimised Bubble Sort".
- copypasterepeat 2y agoI agree. At first I thought it was doing something very simple but I am not so sure anymore. When you check the condition for the swap, you realize it almost works counterproductively while i<j because it keeps pushing smaller numbers in the wrong direction, but then it starts "fixing" those mistakes when i>j. I don't find this intuitive at all.
- deleted 2y ago[deleted]
- InsideOutSanta 2y agoThe problem is that you can look at this and, after a few seconds, think you've formed an intuition on how it must work, but your intuition is wrong. It seems like the only way to really show how weird this is would be by creating an animation that shows how it shuffles entries around. (Edit) I gave it a shot: https://jsfiddle.net/odwh6cL5/45/ https://jsfiddle.net/odwh6cL5/45/
- varunneal 2y agovery beautiful simple animation. Good visualization of the proof of the algo; namely, that at each step i of the outer loop the first i elements are sorted (this is easy to show via induction)
- zamalek 2y agoThis immediately made me wonder if there's some grand unified sorting algorithm, from which all other sorting algorithms can be derived. Could we somehow turn this thing into a quicksort, for example?
- Marazan 2y agoYou are getting worse closer to sorting networks with that supposition https://en.m.wikipedia.org/wiki/Sorting_network https://en.m.wikipedia.org/wiki/Sorting_network
- teddyh 2y agoIt certainly is the most clickbaity title I have ever seen on an actual paper.
- jlarocco 2y agoI don't see why it's at all surprising. Each iteration of the outter loop restuls in the smallest element moving into `A[i]`. And then the first `i` iterations of the inner loop are just wasting time.
- ColinWright 2y ago> Each iteration of the outter loop moves the smallest element into `A[i]`. The first `i` iterations of the inner loop are just wasting time. In the first iteration of the outer loop, i=1, and in that case the inner loop moves the largest element into A[1]. So I don't think you can be correct.
- anonymousd3vil 2y agoThis is similar to bubble sort but with the largest element appearing at the beginning index. Its a reverse Bubble Sort.
- ColinWright 2y agoExcept that when the routine finishes, the smallest element is in A[1].
- daneel_w 2y agoIt just might be the simplest sorting algorithm ever. But it's still just an unoptimized insertion sorter, and it's not novel. One would often come across this in computer books from the 80s teaching basic programming concepts and techniques in, well, BASIC.
- egorfine 2y ago[flagged]
- breaker-kind 2y agowhat?
- Gannalech 2y ago[flagged]
- egorfine 2y agoNothing to do with the original article. This was my attempt at a joke. A totally failed attempt, for which I will have to endure shame and karma hits as it is too late to hide my stupid comment.
- egorfine 2y agoThis was a totally failed attempt at a joke.
- meroes 2y agoIt’s one of those paradoxes where it’s almost funny again
- bigbacaloa 2y agoStudents often produce this algorithm by mistake in first year programming. It works in spite of the fact that they don't know what they are doing.
- Gannalech 2y ago[flagged]
- lolbert6 2y agoshouldnt u b fingerin ur peehole in line @ walgreen
- jp57 2y agoI love this paragraph from the paper: There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(n2) time, whether worst-case, average-case or best-case. It unnecessarily compares all pairs of positions, twice (but see Section 3). There seems to be no intuition behind it, and its correctness is not entirely obvious. You certainly do not want to use it as a first example to introduce students to sorting algorithms. It is not stable, does not work well for external sorting, cannot sort inputs arriving online, and does not benefit from partially sorted inputs. Its only appeal may be its simplicity, in terms of lines of code and the “symmetry” of the two loops.
- teach 2y agoI used to teach this to beginners all the time. I called it "exchange sort", though I'm not sure where I ever got that name from. Beginners to sorting are often still somewhat struggling with for loops (especially the three-part C kind), struggling with indexing an array, struggling with swaps. It's overwhelming. This is kind-of like pseudocode for a simple sort -- it has the same rough outline, but no tricky bits. It allows them to get their brains around the basic algorithm, and only after that you trace through an execution on the board to show them that it wastes a lot of time moving things around. Then you can show them insertion sort as an optimization, and from that move on to fancier ones.
- justinpombrio 2y agoCan you give a reference to your teaching materials? The way this sort works is bizarre enough that I'm curious what you said about it. (Also to verify that this is actually the algorithm you taught, given how many other people thought it was something else.)
- wrsh07 2y agoNote that they define algorithm 2 (see figure of said name) as Exchange Sort, which is distinct from the algorithm they present
- jp57 2y agoThe sort in the OP isn't Exchange Sort, though. In exchange sort the inner loop runs from i+1 to N, not from 0 to N, and the swap order is transposed.
- deleted 2y ago[deleted]
- mathteddybear 2y agoIt is computer science folk-lore. Pretty sure I read about it in some popular computer magazine in 90's.
- deleted 2y ago[deleted]
- smusamashah 2y agoIt's more like an insertion sort when visualized https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZgV2gFwJYHsIwgUwO4DK6ATsgBTDHEA0MAJscHgJQwDeAUDFJiMtjAC8MSsQB0AGxwQA5sgAWAbi5wSMMlP6pBABkUxUAHgj7UAajOtOMeGo05+AK137Hx1xatcbqOOtEA2qgAujCGIlQBjsFeNjYgeMAADhRUtKi0jszKcSKJqPwMTKk0MADM6dRZOTYAvt71MPW1QA https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ... I made this tool to vi's sorting algos long time ago.
- roxolotl 2y agoThis is an awesome tool. I noticed a really fun bug here where if you start a new faster sort before a slower sort finishes the slower sort keeps going and you end up with a the two sorts running at the same time, I think against different sets of values. Don't know if I'd bother fixing it because the output is neat
- layer8 2y agoDiscussed at the time (318 comments): https://news.ycombinator.com/item?id=28758106 https://news.ycombinator.com/item?id=28758106
- clearleaf 2y agoAre these the world's most crispy fries?
- fb03 2y agoIt's delay sort delay(N); append_output(N) that's it.
- deleted 2y ago[deleted]
- olives 2y agoHere's one way to intuitively think about this algorithm: ICan’tBelieveItCanSort(A[1..n]) for i = 1 to n do for j = 1 to n do if A[i] < A[j] then swap A[i] and A[j] Example: 3412 // i=1 4312 // i=1 -> i=2 3412 // i=2 -> i=3 1432 // i=3 1342 // i=3 -> i=4 1243 // i=4 1234 // i=4 1) After an outer loop of i is finished, the first i elements are in ascending order. (For example, in the fifth line above after i=3 is finished, the first 3 elements are "124") 2) At some point, the outer loop will point to "1", and "1" will be compared to the 1st position. Then, "1" will be placed in the 1st position and remain there forever. (For example, this happens in the 3rd line above) 3) After the outer loop points to "1", at some point it will point to "2" which will be compared to the 2nd position. (Proof: when the outer loop pointed to "1", if "2" was on the right of "1", then the statement is obvious; if "2" was on the left of "1", then it would be in the 1st position by (1), so again the statement holds.) Then, "2" will be placed in the 2nd position and remain there forever. 4) After the outer loop points to "2", at some point it will point to "3" which will be compared to the 3rd position...
- tombert 2y agoI love this paper; it's extremely easy to read, but still gets into rigorous proof. Despite their explanation, I still had to hack together something in Java and step through it with a debugger for it to actually make sense to me. Once I did it worked fine, and after looking through each iteration I more or less got it. Here's the code if anyone wants to look at it [1], though just a disclaimer that I wrote this in like ten minutes just to hack something so it's not beautiful or anything like that. It's so simple that I don't think I made any mistakes though obviously if I did let me know and I'll be slightly embarrassed. [1] https://gist.github.com/Tombert/993ada32270f809bdaa6452065f84bf7 https://gist.github.com/Tombert/993ada32270f809bdaa6452065f8...
- casey2 2y agoExtremely common pattern in the shell world. I'd be very surprised if this hasn't been published before 2021. for i in {1..10} ; for j in {1..10} ; [ $a[$i] -lt $a[$j] ] && t=$a[$i] && a[$i]=$a[$j] && a[$j]=$t ; echo $a As for intuition the only thing I can come up with is that better than "it's a double for loop with a cmp and a swap, of course it will sort" is that after every i_th loop the 1..i_th elements are sorted.
- bigprovolone 2y agoNot sure if I missed it, but did anyone look into Knuth's volume 3 to see if it shows up there ? Don't have my copy handy