@queerlilhayseed@piefed.blahaj.zone
2026-09-01 14:54 UTC
Replies (5)
-
@14th_cylon@lemmy.zip 2026-09-01 15:21
That is just a bubble sort, except the comparisons are done in different order than conventional bubble sort…
-
@pelya@lemmy.world 2026-09-01 16:01
I would expect something worse than bubble sort. No idea whether it will even work: void reverse(auto A, int start, int end) { for (int i = 0; i < (end - start) / 2; i = i + 1) { auto tmp = A[start + i]; A[start + i] = A[end - i]; A[end - i] = tmp; } } for (int j = 0; j < N; j = j + 1) { for (int i = 0; i < N; i = i + 1) { if (A[i] < A[i + 1]) { reverse(A, i, N); } } }
-
@chamaeleon@fedia.io 2026-09-01 18:08
Seems straightforward enough. For j values of 1 to i it will not do anything because the largest element in the array has already been moved to position i in some earlier iteration in the i loop. For j values greater than i it then proceeds to find the largest remaining element place in position i.
-
@shape_warrior_t@programming.dev 2026-09-02 11:54
As the addendum to the paper points out, this is more like insertion sort (with i and j in a confusing order) than bubble sort. The actual “important” part of the algorithm happens when j = i after the first outer iteration.) (I think the page about people misremembering bubble sort is also worth looking at.) Honestly, I think this might actually be “better” than bubble sort, in the sense that at least it’s incredibly easy to remember and not that hard to get correct. The only place where you could realistically mess up is confusing the relative order of i and j – and any amount of nontrivial testing will immediately show the error, since it reverses the sort order. I’d probably reach for this if I, for whatever insane reason, had to code up a sorting algorithm by hand for some task where O(n^2) sorting was acceptable performance-wise. “Sort a list of 10 items in a very primitive programming language”-type deal. (Now that I say that, I’m kind of tempted to use it in some example program for my own in-development programming language, which currently doesn’t have a builtin sort function…)
-
@mesamunefire@piefed.social 2026-09-02 17:38
My favorite sorts are random sort (toss them up, see where they fall. are they sorted?) and bead sort (connect 4 sort). One is potentially O(1) sort and the other is potentially O(n). haha. But in practice they are terrible. Love it. This sort is neat too.