20 ms·
I can’t believe that I can prove that it can sort
- MattPalmer1086 4y agoInteresting. It is a bit counter intuitive at first but not too hard to see how it works. After the first main loop, the first item will be the biggest item in the list. The inner loop, as it always starts from 1 again will gradually replace the bigger items with smaller items, and so on.
- JadeNB 4y ago> After the first main loop, the first item will be the biggest item in the list. > The inner loop, as it always starts from 1 again will gradually replace the bigger items with smaller items, and so on. I think the "and so on" is the point. To put it more precisely, I think that anyone (with a suitable familiarity with the tools) can prove formally that "after the first main loop, the first item will be the biggest item in the list"; but I think that it might take a bit more work to prove the "and so on" in a way that satisfies a formal prover. (As to the intuition—I can buy that the "and so on" part is reasonably intuitive, but only at a level of intuition that can also believe wrong things. For example, just always replacing bigger items with smaller items doesn't guarantee you'll get a sorted list!)
- MattPalmer1086 4y agoSure, formal proof would be a lot harder. I just didn't find it quite as surprising that it works as the article implied.
- roenxi 4y agoIf it looks "obviously wrong" the quick proof that it works ... the j loop will move the largest unsorted element in the array into a sorted position. Since the i loop executes the j loop n times, the array must be sorted (since the n largest elements will be in the correct order). EDIT ^W^W^W Nope, I'm wrong. I did a worked example on paper. I think the devious thing here is the algorithm looks simple at a lazy glance. To sort: 4-3-6-9-1, next round pivot for the i loop in []. [4]-3-6-9-1 9-[3]-4-6-1 3-9-[4]-6-1 3-4-9-[6]-1 3-4-6-9-[1] 1-2-3-6-9 & sorted I can see that it sorts everything to the left of a pivot, then because it does that n times it comes to a sorted list. A reasonable proof will be more complicated than I thought.
- blueflow 4y agoThis somewhat looks like bubble-sort minus the early exit.
- zajio1am 4y agoIt is just quirky insert-sort. In each outer cycle, it inserts value originally from the A[i] position to already sorted sequence A[1]..A[i-1], while using A[i] as a temporary variable to shift higher part of the sorted sequence one position up.
- MrYellowP 4y agoIt is BubbleSort. At least that's how I've learned it in the 80s.
- phkahler 4y agoThe list on the left (index less than i) is always sorted. The ith element is inserted by the j loop and the rest of the list is shifted right by one element by repeated swapping with the ith position. Nothing to the right changes because the ith element is the max of the entire list, which seems to be a red herring for analysis.
- smusamashah 4y agoHere is how it looks. https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZgV2gFwJYHsIwgUwO4DK6ATsgBTDHEA0MAJscHgJQwDeAUDFJiMtjAC8MSsQB0AGxwQA5sgAWAbi5wSMMlP6pBABkUxUAHgj7UAajOtOMeGo05+AK137Hx1xatcbqOOtEA2qgAujCGIlQBjsFeNjYgeMAADhRUtKi0jszKcSKJqPwMTKk0MADM6dRZOTYAvt71MPW1QA https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ... If you compare it with both Insertion and Bubble sort. You can see it looks more like insertion sort than bubble sort.
- iib 4y agoI guess it can be thought of as an unoptimized insertion or bubble sort. I think it is very possible to write this algorithm by mistake in intro compsci classes when you try to code a bubble sort by heart. I would think TAs may have many such instances in their students' homework.
- mmcgaha 4y agoI am guilty. I wrote this sort for a gnu screen session menu years ago and even named my function bubsort.
- naniwaduni 4y agoThere's a surprisingly large class of "sorts people accidentally write while intending to write a bubble sort". This one is kind of special, though, since it's somehow more offensive to intuition than bubble sort itself.
- Dylan16807 4y agoBubble sort is offensive to intuition? I would have said it was the most intuitive, because each step is very simple and you only have to remember one numeric variable in your core loop.
- naniwaduni 4y agoBubble sort's inner loop is so hilariously pessimal that it's incredibly easy to accidentally write an insertion sort because you intuition tells you it can't possibly be intended to be that bad.
- hobo_mark 4y agoWow, I wish we had these built-in provers in VHDL (which is basically Ada in sheep's clothing).
- jwilk 4y agoThe paper discussed on HN: https://news.ycombinator.com/item?id=28758106 https://news.ycombinator.com/item?id=28758106 (318 comments)
- eatonphil 4y agoThis is a fantastic post! It's great to have a concrete example of proving a not-trivial algorithm. And somehow this Ada code feels more approachable to me than HOL4 and other functional proof assistants I've looked at. While it's been on my list for a while, I'm more curious to try out Ada now.
- Jtsummers 4y agoIt'll take you less than a week to get proficient enough in it to make something useful, or at least interesting. It's a very straightforward language, overall. https://learn.adacore.com/ https://learn.adacore.com/ - Pretty much the best free source until you're actually ready to commit to the language. The "Introduction to Ada" course took me maybe a week of 1-2 hours a day reading and practicing to go through. There's also a SPARK course that takes a bit longer, but is also interactive. The language reference manuals for 2012 and 202x (which should become Ada 2022): http://www.ada-auth.org/standards/ada12.html http://www.ada-auth.org/standards/ada12.html http://www.ada-auth.org/standards/ada2x.html http://www.ada-auth.org/standards/ada2x.html
- touisteur 4y agoTwo of the most interesting things that trickled down during the design of Spark2014: 1- contracts are written in the same language as the code to be checked/proved. This made important to add expressive features to the language (for all / for some: quantifiers! expression functions, if- and case-statements and more recently the new delta-aggregates notation): these additions make the language far more expressive without too much loss of readability. 2- executable contracts: most contracts can be checked at runtime or proved. And the escape hatch (code only present for proof) is 'ghost' code which is also a nice addition. Lots of little nifty additions to the language, from just 'thinking in contracts' or 'designing for probability'.
- FrozenVoid 4y agoCombsort is far more elegant and faster algorithm. I've wrote a type-generic combsort a while ago here: https://github.com/FrozenVoid/combsort.h https://github.com/FrozenVoid/combsort.h (Combsort as well as mentioned algorithm also consists of two loops and a swap)
- JadeNB 4y agoI don't think that the goal here is to show a fast and elegant sort, but rather to show that a sorting algorithm that seems like it can't possibly work actually does. That is, probably no-one will learn from this article how to sort better, but hopefully people will learn from this article how to formally prove things (e.g., about sorting) better.
- touisteur 4y agoYes (co-author here) that was exactly the point. Thanks for putting it clearly.
- carlsborg 4y agoVaguely remember seeing this in the first few chapters somewhere of Spirit of C by Mullish and Cooper.
- petercooper 4y agoCan confirm. It's on page 243, in the "Arrays" chapter, and is referred to as the "exchange sort." The actual code is: /* Sort the array for (i = 0; i < array_size - 1; i++) for (j = i + 1; j < array_size; j++) if (array[i] > array[j]]) { int temp = array[i]; array[i] = array[j]: array[j] = temp; } So that's from the late 80s.
- Jtsummers 4y agoThat's not the same sort as in the article. Two key differences: 1. j in the article runs from 0 to array_size-1 (if done in C like this, in the article it's a 1-based array so 1 to array_size). This sort has j run from i+1 to array_size-1. 2. The swap condition is reversed. In the article's sort the swap happens when array[i] < array[j].
- twawaaay 4y agoI actually used this algorithm a decade ago to implement a log-based, transactional database system for an embedded system with very low amount of memory and requirement that all memory be statically allocated. To the frustration of the rest of the development team who first called me an idiot (I was new) then they could not make quicksort run as fast on inputs that were capped at something like 500 items. Apparently, algorithmic complexity isn't everything.
- texaslonghorn5 4y agoIf I understand correctly, you would just run the n+1 th outer loop to insert the new item each time?
- deleted 4y ago[deleted]
- delecti 4y agoI fee like anyone who was surprised that algorithmic complexity isn't everything, probably didn't totally understand it. The assumptions (like ignoring constants) are straight out of calculus limits. That (+10000) on the end doesn't mean anything if you're sorting an infinite list, but it means a lot if you're sorting 15 (or in your case 500) entries.
- twawaaay 4y agoWell, it actually is kinda worse (or better, depends how you look at it). It is not necessarily +10000, it can also be something like x5000. Because CPUs really, really, really like working short, simple, predictable loops that traverse data in a simple pattern and hate when it is interrupted with something like dereferencing a pointer or looking up a missing page. So your super complex and super intelligent algorithm might actually be only good on paper but doing more harm to your TLB cache, prefetcher, branch predictor, instruction pipeline, memory density, etc. So there is this fun question: "You are generating k random 64 bit integers. Each time you generate the integer, you have to insert it in a sorted collection. You implement two versions of the algorithm, one with a singly-linked list and one with a flat array. In both cases you are not allowed to cheat by using any external storage (indexes, caches, fingers, etc.) The question: in your estimation, both algorithms being implemented optimally, what magnitude k needs to be for the linked list to start being more efficient than array list." The fun part of this question is that the answer is: NEVER.
- deleted 4y ago[deleted]
- dgan 4y agoSo, Lionel knew how to implement a 3D Renderer, but had no clue about O(n) complexity neither other sorting algorithms? I am buffled
- fn_t_b_j 4y ago
- im3w1l 4y agoThat's self-taught for you. Will know some advanced stuff, and miss some basics depending on what they found interesting or useful.
- touisteur 4y agoWell, Hi there, it me. Back then I was 17 and wading through software rendering so (light) mesh tessellation, triangle projection (twice, for a stereoscopic anaglyph renderer), triangle filling, texture mapping, with at most 300 objects, all in crappy crashy C (first with VESA, then SDL eased my life...) with lots of misunderstandings about pointers. I was welllll over my head with complex stuff, and sorting didn't appear in the profiles, so... I guess you can call that profile-guided learning? I had the formal training, later on, and even then it didn't stick until I faced the actual complexity problem head-on. I'll never forget that whole weekend with my AMD Athlon 900 at 100% CPU sorting a 200 000 words dictionary... It was still not finished on Monday. Implemented (a very primitive) insertion sort and it was done in less than 2 minutes... That was my 10000-a-day day https://xkcd.com/1053 https://xkcd.com/1053
- Agingcoder 4y agoThe exact same thing happened to me, and this is how I discovered algorithmic complexity. Sorting my triangles took forever (I saw it in the profile, taking a whopping 90% of the time ) and I eventually figured there might be a proper sorting algorithms out there. I was at the same time happily churning out assembly code, talking to the vga card, writing a dos extender, etc. You can actually do quite a few things without formal education!
- ufo 4y agoThe comments so far have tended to focus on the proof itself, but for me the coolest part of the blog post were the formal methods. Does anyone here also use SPARK for this sort of thing? Are there other formal methods tools you'd use if you had to prove something like this?
- im3w1l 4y agoYeah, I see this as a very interesting reply to the TLA+ post. Might spend my evening diving into Ada and Spark. Edit: Some things I noticed. The package gnat-12 does not have gnatprove. Ada mode for emacs requires a compilation step that failes with gnat community edition. With alire there is no system gnat so it cannot compile it (quite possible I'm missing something). In the end I gave up on using emacs. Gnatstudio wouldn't run for me until I realized it needed ncurses. It also had some unhandled exceptions for me (raised PROGRAM_ERROR : adjust/finalize raised GNATCOLL.VFS.VFS_INVALID_FILE_ERROR: gnatcoll-vfs.adb:340), but in the end I managed to get it up and running. Edit2: After playing around with it, I'm extremely impressed with what spark can do. I made a function to add 7 to numbers. Tried putting a post condition that the return value is bigger than input. "Nuh uh, it could overflow". Ok so I add a pre condition that numbers must be less than 100. "Uhm, buddy you are passing in 200 right there". This is useful stuff for real and easy to write too.
- yannickmoy 4y agoyou can ask Alire to install the latest GNAT it built, or to use another version installed on your machine, see https://alire.ada.dev/transition_from_gnat_community.html https://alire.ada.dev/transition_from_gnat_community.html It also explains how to install GNATprove: ``alr with gnatprove``
- im3w1l 4y agoSorry if it was confusing I kind of jumped between the issues I had with various approaches. I did manage to get gnatprove through alire through just that command, it was the apt gnat that didnt have gnatprove. What I wasn't sure how to correctly do with the alire install was cd ~/.emacs.d/elpa/ada-mode-i.j.k ./build.sh ./install.sh Actually I didn't get that working with any of the options I tried I guess.
- asrp 4y agoAfter each outer loop iteration, A[:i] (the array up to i) is in ascending order with the max of A at A[i]. This is true the first iteration since max(A) is eventually swapped to A[1]. This is true in subsequent iterations since during the ith iteration, it inserts the next element, initially at A[i], into A[:i-1] and shift everything up with swaps with A[i] so A[:i] is sorted, with the max of A moved to A[i]. After that no more swaps happen in the ith iteration since A[i] contains the max of A.
- ermir 4y agoIsn't the sorting algorithm in question the famous BubbleSort? I understand the value of formally proving it works, but why is the name mentioned nowhere?
- deleted 4y ago[deleted]
- justusthane 4y agoNope - here's the original paper on the algorithm in question: https://arxiv.org/pdf/2110.01111.pdf https://arxiv.org/pdf/2110.01111.pdf
- palotasb 4y agoNo, it's not. Previously discussed on HN here: https://news.ycombinator.com/item?id=28758106 https://news.ycombinator.com/item?id=28758106 (https://arxiv.org/abs/2110.01111 https://arxiv.org/abs/2110.01111)
- smcl 4y agoIt feels similar at first blush but it's not really. In bubble sort you compare/swap adjacent elements, and exit if you make a pass through the collection without making any changes. Whereas this will compare/swap the element at every index to every other index, and just exits when it's done performing all those comparisons.
- ufo 4y agoIt's actually closer to insertion sort.
- drdrek 4y agoHe starts from the wrong axiom that its hard to prove and creates a lot of nonsense over that. Its requires just two induction proofs: - One that for I=1, after N comparisons the largest number is at position 1 (Proven with induction) its the base case - The other, that for any I=n+1 if we assume that the first n slots are ordered we can treat n+1 as a new array of length N-n and solve using the base case proof. Talking about computer science and not doing the bare minimum of computer science is peak software engineering :)
- phkahler 4y agoI thought his goal was to get the prover to prove it without understanding it himself. By realizing the low-indexed portion is always sorted, you've already proved the algorithm yourself and the prover is just checking for bugs in your logic. I'm not saying the proof isnt valuable, just that it's not magical and actually requires the user to understand the majority of the proof already.
- leereeves 4y agoThis algorithm is surprising and interesting because it doesn't work at all like it at first seems to. The low-indexed portion is sorted, but isn't guaranteed to contain the lowest or the highest i elements of the list (except when i=1), and the list is ultimately sorted in decreasing, not increasing order. The final sort doesn't occur until the last iteration of the outer loop when the inequality is reversed (the interesting variable, j, is on the right). Because of that, the proof outline discussed here doesn't work. Consider what happens if the unique smallest element starts at position n. It is placed at the start of the list (the correct final position) in the final iteration of the outer loop (i=n), and not before. Proof (for simplicity the list is indexed 1 to n): Let A[n] < A[k] for all k != n in the initial list. Elements are only swapped when A[i] < A[j]. If i != n and j = n, then A[i] > A[n] = A[j], so A[n] is not swapped. Then, when i = n and j = 1, A[i] = A[n] < A[1] = A[j], so A[1] and A[n] are swapped, placing the smallest element in position 1 at last.
- School-Cotton 4y ago
- jeffhuys 4y agoSmall sort implementation in ES6: const args = process.argv.slice(2).map(Number); for (let i = 0; i < args.length; i++) for (let j = 0; j < args.length; j++) if (args[i] < args[j]) [args[i], args[j]] = [args[j], args[i]]; console.log(args.join(' ')); Didn't expect it to be actually that simple, but now that I wrote it, it makes complete sense. To PROVE it, is another thing. Good work.
- donatj 4y agoIs this not a standard sorting algorithm? If I'm not mistaken this is my coworkers go to sort when writing custom sorts.
- Jtsummers 4y agoIt manages to be more inefficient than most, and will even disorder and then reorder an already sorted input. Bubble sort (a very low bar to beat) doesn't even do that. If you've only got a small number of items, it doesn't matter unless you're sorting a small number of items a large number of times.
- deleted 4y ago[deleted]
- ki_ 4y agoa "new sorting algorithm"? Pretty sure it existed 50 years ago.
- prionassembly 4y agoI taught myself this exact algorithm at 8 or 10 by sorting playing cards (we established an order for the kind, diamond < leaf < spades < heart) in a very very very long plane trip where I had neglected to bring comic books or something.
- rationalfaith 4y ago
- fweimer 4y agoIsn't the proof incomplete because it does not ensure that the result is a permutation of the original array contents? Just overwriting the entire array with its first element should still satisfy the post-condition as specified, but is obviously not a valid sorting implementation.
- touisteur 4y agoIt was touched upon in the post: 'Tip: Don’t prove what you don’t need to prove' (and surrounding text). With a link on another proof for another sorting algorithm.
- yannickmoy 4y agoand there are actually multiple ways to prove that the result is a permutation of the entry, either by computing a model multiset (a.k.a. bag) of the value on entry and exit and showing they are equal, or by exhibiting the permutation to apply to the entry value to get the exit value (typically by building this permutation as the algorithm swaps value, in ghost code), etc. but none of this makes a good read for people not already familiar with program proof tools.
- fdupress 4y agoEvery time somebody proves that a sorting algorithm sorts, they forget to prove that the algorithm doesn't just drop values or fill the entire array with 0s (with fixed-length arrays, as here). On paper: "it's just swaps" Formally: "how do I even specify this?" (For every value e of the element type original array and the final array have the same number of occurrences of e. Show that that's transitive, and show it's preserved by swap.)
- touisteur 4y agoHi, co-author here. We actually touched upon this subject in the article: 'Tip: Don’t prove what you don’t need to prove' and surrounding text. Also previous comment by Yannick: https://news.ycombinator.com/item?id=31980126 https://news.ycombinator.com/item?id=31980126
- fdupress 4y agoLooked for it and missed it. And thanks for writing this up, by the way. Having people less familiar with formal methods try and write up their experiences is, I think, much more effective at letting people in than having experts try and write tutorials.
- deleted 4y ago[deleted]
- MrYellowP 4y ago> published at the end of 2021 I'm so confused. That "new" algorithm is just BubbleSort?
- Jtsummers 4y agoAs addressed in other comments in this thread and past threads on this sort (when the paper came out), it is not bubble sort. Bubble sort only compares adjacent items and swaps them if they are in the wrong order. This has the effect of "bubbling" the largest value to the top (the way it's often written, could also reverse it to push the smallest down first). This sort is like a worse performance version of insertion sort. But insertion sort creates a partition (and in doing this performs a sort) of the first i+1 items, with i increasing until the entire sequence is sorted. This one will scan the entire sequence every time on the inner loop instead of just a subset of it and usually perform more swaps.
- OJFord 4y agoWhy is this algorithm at all surprising? (I'm really not trying to brag - I assume I must be missing something, that I'm naïve to think it obviously works, and it actually works for a different reason.) In plain English - 'for every element, compare to every element, and swap position if necessary' - .. of course that works? It's as brute force as you can get?
- Asooka 4y agoThe comparison is not the way you'd expect. Index j goes past index i, but the comparison doesn't change. What you propose is a condition more like if ((a[i] < a[j]) != (i < j)) swap(a, i, j) ; Which obviously works. The surprising algorithm sorts even though it swaps elements that are already ordered.
- OJFord 4y agoOk, I think I see why it's a bit weird '1,2,3 when i=1 and j=3 it swaps them anyway' sort of thing? But i-loop comes through 'afterwards', so when i=3 (value now 1) and j=1 (3) it sets them straight. It still seems quite intuitive, but I think I cheated by skimming over it initially and thinking it was clear, whereas actually I've thought about it more now. (Not to compare myself to anything like him, I'm no mathematician at all, but I'm reminded of an amusing Erdós anecdote in which he apparently paused mid-sentence in some lecture, left the room, and came back some time later continuing 'is clearly [...]' or similar!)
- YetAnotherNick 4y agoIf the second loop is from j = i to n, it is easy to see that it will sort in decreasing order. But notice j = 1 to n, then suddenly it will sort in increasing order
- shp0ngle 4y agolook again at the comparison direction. It is opposite! It works but not as you think it does.
- Stampo00 4y agoI've been watching those mesmerizing YouTube videos visualizing sorting algorithms lately. The header of this article uses a screen cap from one of them. Them: So what shows do you watch? Me: ... It's complicated. There are a lot of different sorting algorithms. Like, a lot, a lot. As I watch them, I try to figure out what they were optimizing for. Some only scan in one direction. Some only use the swap operation. Some seem to do the minimum number of writes. Some are incremental performance improvements over others. When I see an algorithm like this, I don't assume the person who wrote it was an idiot. I assume they were optimizing for something that's not obvious to me. Its only modifying operation is swap, so maybe that operation is faster than an arbitrary insert for whatever system or data structure they're using. There are no temporary variables besides loop counters, so maybe they're on a memory-constrained environment. There's barely any code here, so maybe this is for a microcontroller with precious little ROM. Or maybe they're applying this as a binary patch and they have a strict ceiling to the number of ops they can fit in. Or maybe it's just the first sorting algorithm they could think of in an environment that doesn't ship with one and the performance is adequate for their needs. In that case, it's optimized for developer time and productivity. And honestly, it's a far more elegant algorithm than my "naive" version would be. These are all valid reasons to use a "naive" sorting algorithm.
- zoomablemind 4y agoTFA seems to be a somewhat wasteful version of an algo which in my mind I call 'sinkersort' or 'minsort': for (i=0; i<n; ++i) for (j=i+1; j<n; ++j) if (a[j] < a[i]) swap(a[j], a[i]); Here the inner loop basically finds a min value of the remaining subset. This progressively fills the array in the sorted order. The number of comparisons is bound by n^2/2 vs n^2 of TFA.
- palunon 4y agoYours looks like selection sort but with more swapping. The one in TFA isn't, for one crucial reason: the comparison is the other way around... And yet, it sorts.
- zoomablemind 4y ago> Yours looks like selection sort but with more swapping... Well, shooting for the simplicity (as posited in the Fung's arxiv paper) -- this one is on par with TFA and somewhat simpler in expression than the selection sort. This is also direct, less 'magical' and indeed less wasteful than TFA. So for those roll-your-own-sort moments I'd rather remember this one instead.
- zoomablemind 4y agoBy the way, the TFA algo is equivalent to: for (i=0; i<n; ++i) for (j=0; j<(i ? i : n); ++j) if (a[i] < a[j]) swap(a[i], a[j]); Once the max has been swaped in, further inner iterations past i (the position of max) are redundant. However, we can go even further: for (i=0; i<n; ++i) for (j=0; j<i; ++j) if (a[i] < a[j]) swap(a[i], a[j]); This dispenses with the explicit max swap and simply does progressive insertion. Curiously, in such transformed form the algo echoes the 'selection sort' from my previous post, performs equivalently too (wrt ncmpr, nswp).
- nephanth 4y agoArticle says it is better to actually read the paper instead of trying to figure it out. I disagree on that. It is a good exercise to try to prove it by yourself and it was actually quite fun Main mistakes author makes though - trying to prove it works without first understanding why / how it works. Always simulate test-runs on paper / in your head before - trying to prove on machine first. Always make sure you can do the proof on paper first. Then and only then should you battle with your verifier / solver to get it to understand your proof