Lots 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".
The 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.
The visualization helped me realize something: The index doesn't change after the swap, so you always end up with the biggest number "in hand" after a full deeper level iteration loop.
very 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)
I 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.
>In Bubble Sort you only ever compare adjacent items. Here you don't.
This is the first thing I noticed and it pretty much says it all. It is not bubble sort because there are no bubbles bubbling to the top. Instead it compares every possible element pair combination.
> 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".
I can try to explain that. The algorithm really is doing a bubble sort, with some unnecessary extra work added. It also does a bit of necessary extra work.
Here is the useful work done by the algorithm:
1. First, preprocess the list so that the maximal element occurs first. (It's a 1-indexed list, so position 1 holds the highest element of the list.)
2. Now, we consider an invariant: the part of the list up to (and including) the maximal element is always sorted. Right now that consists of indices 1-1, and since that range contains only one value it's necessarily sorted. We will use a variable ("i") to remember where the maximal element is.
3. Now, the outer loop: we start at the index immediately after the maximal element, index i+1. Whatever value is in there, we bubble it to the left (this is the inner loop), in the manner of a standard bubble sort: we compare it to index i, and if it's lower (which is always, since i holds the maximal element), we swap. Then we compare index i to index i-1, and so on. Once we find an element that is smaller than the one we've been bubbling to the left, we stop, and our invariant is restored: the list up to the maximal element is still sorted. But the space covered by the invariant has increased by one slot. We increment i.
4. The loop continues until i points to the last slot in the list, at which point we're done. The invariant tells us the the list up to i is sorted, and since i points to the last value in the list, the whole list is sorted.
-----
The algorithm I've described sends i forward from the beginning to the end of the list and j backwards from i+1 to the beginning of the list. The algorithm in the paper does all the same work, but it also does more work, instead having j cross the entire list every time. (It also sends j forwards, like i, but this doesn't matter.†) The only reason for this is to make the algorithm simpler to write down. This is why it's "unoptimized bubble sort". Note that, in the algorithm of the paper, once the maximum value has been swapped into i, the check A[i] < A[j] can never succeed, but we ignore that and keep advancing j instead of just terminating the j loop. This looks especially stupid because the maximal value will always occur before i (except when i = 1, which is the stage that, in my algorithm, is called "preprocessing").
In a bubble sort, if your cursor is at 5, and you want to move A[6] to index 3, you need to make 3 swaps and 3 comparisons. In the paper's sort, when your cursor is at 5 and you want to move A[6] to index 3, you need to make 3 swaps and n comparisons, where n is the length of the full list.
-----
If you're interested in why the j loop is the same thing as a bubble sort, here's an expansion on the example above:
We're in the process of bubble sorting [1 4 8 11 24 5], looking at the 5. Because 5 is more than 4 but less than 8, we want it to ultimately end up at index 3. Everything else will shift up by one index to accommodate this.
In a bubble sort, we swap the 5 down into index 5, then we swap the 5 down into index 4, and then we swap it down into index 3.
swap(&a6, &a5);
swap(&a5, &a4);
swap(&a4, &a3);
In the paper's sort, we do exactly the same thing from the other direction:
int* temp;
*temp = a6; /* we want to put this into its correct position */
swap(&a3, temp); /* done, but we need to remember what was in a3 so we can swap it up to a4 */
swap(&a4, temp); /* done, but now we need to remember what was in a4 so we can swap it up to a5 */
swap(&a5, temp); /* take a guess... */
swap(&a6, temp);
but there's a slight optimization where instead of using a temporary variable to hold the values we're swapping, we just use the space after the maximal element (which makes `swap(&a6, temp)` redundant - after the optimization, those are the same address).
† It matters a little bit - a bubble sort is free to terminate the inner loop as soon as the value being bubbled has found its correct position. But in the paper's algorithm, we have to find the correct position first, which is done by scanning every index that contains a lower value until we eventually find the first one that doesn't. That work is optimized out of a bubble sort. However, since the paper's sort is committed to scanning the entire list in the inner loop anyway, the fact that the order of bubbling is wrong doesn't require any more extra scanning beyond what they've already committed to.
This is a strange argument to me, because the single most critical aspect of a bubble sort is the locality.
Bubble sort only ever compares adjacent elements. It only ever swaps adjacent elements. This is what makes bubble sort optimal (within constant factors) for an external sort on a tape drive. This is why anything else isn't a bubble sort.
Here's an algorithm (in Python) that is exactly equivalent to the one in the paper:
def pseudobubble(lst):
n = len(lst) # give a name to the list length
for i in range(n-1, 0, -1): # i will range from n-1 down to 1 inclusive
if lst[i] > lst[i-1]:
swap(lst, i, i-1) # high values bubble down
for i in range(1, n): # 1 to n-1 inclusive
for j in range(i, 0, -1): # i down to 1 inclusive
if lst[j] < lst[j-1]:
swap(lst, j, j-1) # low values bubble down
The first pass of this algorithm (bubbling high values down, one time only) may do different things than the first pass of the paper's algorithm, but that's not relevant.
All comparisons and swaps in the code you quoted are made between adjacent elements. It's local in a way that behaves very nicely for an external sort on a tape drive.
The code in the paper compares and swaps non-adjacent elements nearly every time. It is absolutely horrible for an external sort on a tape drive. It's just not a bubble sort, nor is it sort of like one in any key behavioral detail.
No, a bubble op bubbles one element into the correct position in a sorted list. If it was restricted to bubbling the maximum or minimum to the end of the list, the full sort would use one bubble, it would complete in linear time, and the list wouldn't be sorted afterwards.
You're correct that this is also a good match to insertion sort, but only conceptually.
(Note that one classic bubblesort pass moves several elements when the data is unsorted - when an element has bubbled as far as it can go, the bubblesort pass picks up the element that blocked it and carries that one further, and this process repeats until the end of the data is reached. For our purposes, there is no difference, because we're bubbling into a perfectly sorted list, so once our initial element stops moving, nothing else can move.)
The bigger difference between an insertion op and a bubble op is in the number of assignments.
This is the chain of operations you get while bubbling:
swap(a5, a6)
swap(a4, a5)
swap(a3, a4)
This is the chain of operations you get while inserting:
temp = a6
a6 = a5
a5 = a4
a4 = a3
a3 = temp
Inserting never does any swaps. But each swap is three assignments, so the bubble in this case does nine assignments to the insertion's five. (And in general, if you need to sink a value n places into the data, bubbling it there will take 3n assignments, and inserting it there will take n+2.) That is the advantage of knowing where you're going before you get there.
> If it was restricted to bubbling the maximum or minimum to the end of the list, the full sort would use one bubble, it would complete in linear time, and the list wouldn't be sorted afterwards.
Yes, one bubble op is linear time. A bubble sort is a sequence of bubble ops on the unsorted portion of the list (which shrinks by one for each bubble op).
Meanwhile an insertion sort is a sequence of insertion ops into the sorted portion of a list. So I agree with your analysis, except that the featured sort is a pessimized insertion sort, not a pessimized bubble sort.
> No, a bubble op bubbles one element into the correct position in a sorted list.
Again, that's an insertion op, not a bubble op. I suppose an insertion op can be thought of as equivalent to a bubble op on an element prepended to a sorted list, but it doesn't make sense to call it a bubble op in the context of bubble sort, since bubble sort doesn't do that.
> For our purposes, there is no difference, because we're bubbling into a perfectly sorted list, so once our initial element stops moving, nothing else can move.
I think this is where you're going wrong. In a bubble sort, a bubble op is never run on a sorted list + 1 element. Instead, it's run only on the unsorted portion of the list.
There are two variations of insertion sort. You are comapring to the swapless insertion sort, the other poster is comparing to the swap basses insertion sort. This is the swap based insertion sort with a small variation.
As discussed, unlike insertion sort it begins by finding the max element and places it first.
Following that it follows normal insertion sort pattern with one change. Insertion sort normally sorts the new element "downward". This sort sorts the new element "upward" from the smallest item. It still uses the same inline temporary slot that insertion sort uses, it's just more notable now because it's inserting the new item "bottom-up".
> Following that it follows normal insertion sort pattern with one change. Insertion sort normally sorts the new element "downward". This sort sorts the new element "upward" from the smallest item. It still uses the same inline temporary slot that insertion sort uses, it's just more notable now because it's inserting the new item "bottom-up".
Well, the reason that's more notable is that doing it upward requires you to use swaps instead of an assignment chain. Going downward, you can remember the value you're going to insert all the way down the chain. Going upward, you're always overwriting a value that you must immediately remember, which is worse.
The number of swaps is nearly the same between Bubble Sort and Can't Believe Sort. For a random list with 100 elements, it's 2505 swaps vs. 2513 swaps.
The number of comparisons is of course about twice as large, because Bubble Sort always does exactly n(n-1)/2 comparisons while Can't Believe sort always does exactly n*n comparisons.
> The number of swaps is nearly the same between Bubble Sort and Can't Believe Sort. For a random list with 100 elements, it's 2505 swaps vs. 2513 swaps.
Why is there any difference? Does the entire difference come from the iteration where i = 1?
> Bubble Sort always does exactly n(n-1)/2 comparisons
Bubble sort can do less than this. When you're bubbling down into a sorted list, and you find a value lower than you are, you can assume that all values below that one are also lower than you are and terminate the inner loop early.
> Why is there any difference? Does the entire difference come from the iteration where i = 1?
Sometimes it's more swaps, and sometimes it's less. The vague pattern looks like Can't Believe Sort does slightly fewer swaps on larger lists, but that could also have been noise.
Why do you expect them to have exactly the same number of swaps?
> Bubble sort can do less than this.
Oh sorry yeah, I implemented bubble sort without any sort of early return, for a more direct comparison.
I expect them to have exactly the same number of swaps in every iteration of the loop past the first one, because they are doing exactly the same thing. It's not just the same number of swaps. It's essentially the same set of swaps, in a different order. In the iteration where i = 1, the number of swaps may differ. Was I wrong about that?
Yeah, 2410 vs. 2509 swaps not including the first iteration. You should try measuring these things yourself, I'm not sure if it's doing what you think it's doing.
Well, I sort of agree with you and sort of disagree.
from random import randrange
def list_swap(lst, i, j):
temp = lst[i]
lst[i] = lst[j]
lst[j] = temp
def icbicsort(lst):
swap_count = 0
n = len(lst)
for i in range(n):
for j in range(n):
if lst[i] < lst[j]:
swap_count += 1
list_swap(lst, i, j)
return swap_count
def bubble(lst):
swap_count = 0
n = len(lst)
# preprocess
# this is intentionally identical to icbicsort with i = 0
for j in range(n):
if lst[0] < lst[j]:
swap_count += 1
list_swap(lst, 0, j)
# go forward, bubbling backward
for i in range(1, n):
for j in range(i, 0, -1):
if lst[j] < lst[j-1]:
swap_count += 1
list_swap(lst, j-1, j)
return swap_count
def cmp(n=100):
alst = []
blst = []
for t in range(n):
value = randrange(65536)
alst.append(value)
blst.append(value)
icb_swaps = icbicsort(alst)
bubble_swaps = bubble(blst)
print(f"icb: {icb_swaps} swaps; bubble: {bubble_swaps} swaps")
# just for completeness
def bubble_classic(lst):
n = len(lst)
sorted = False
while not sorted:
sorted = True
for i in range(n-1):
if lst[i] > lst[i+1]:
sorted = False
list_swap(lst, i, i+1)
return
26 calls to cmp() produced identical swap counts in 24 cases and slight discrepancies (of 2 and 3 swaps, both favoring icbsort) in two cases. (For statistical purposes, this was a manual inspection where I stopped after getting the second discrepancy.)
If you're regularly seeing discrepancies, something is weird. If you're seeing them occasionally, I still think something is weird, but I'm prepared to believe that it's a bug in the code.
I will note, in support of the paper's actual thesis, that I wrote icbicsort() correctly on the first try, and I had to work many bugs out of bubble(). Maybe it's still bugged.
Yeah, this makes sense to me. I started developing some of these similar intuitions while watching a visualization another commenter posted.
Here are some things I realized:
1. The first pass (I think you call it the preprocessing step) is special in that it finds the maximum number and puts it in the first slot. The rest of the algorithm revolves around this max value (or at least I find it helpful to think of it that way). This is also the only time where j going above i makes any difference. After this pass we could stop the j loop when i == j but that would obviously complicate the code.
2. Second pass will always swap items in first and second slots since the first item is bigger than second (if they are equal, nothing happens). As noted in 1., j will keep going past i but it won't do anything since i is now pointing to the largest value in the array and the swap condition will never be met.
3. On third and all subsequent passes the value that a[i] is pointing to will be slotted in its right place in the sorted list that's being formed at the beginning of the array. This might require multiple swaps as j goes up and larger values go into the ith slot. Last thing that happens before j reaches i (so when j == i - 1) is always that the max value gets swapped from i-1 to i. This is basically what the second pass from 2. did.
4. The max value from 1. conceptually serves almost as a sentinel of sorts since it always represents the end of the list we've sorted so far and when j gets to i, it prevents the rest of j loop from doing anything. That's why the code can be so clean, without having to do any index arithmetic or short circuiting or any other complications. It's clean but definitely not simple, since it takes a while to wrap one's head around what's actually happening.
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.
I 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.
Can 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.)
This 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.
> 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.
That's actually not correct at all either. After the first pass makes the largest element the first element, every pass after that is a single iteration of (reverse) bubble sorting the beginning of the array, increasing the array that is sorted. So, the second pass doesn't end up with the largest or smallest of the list, just the smallest of the selected prefix.
Once the iterator reaches beyond the length of the tested prefix, we know every element after it will be smaller because we bubbled the largest element to the iteration point which means we won't do any checks there after. In fact, excepting the first pass, this inner loop can break whenever it sees it is comparing against itself.
It 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.
Yeah, 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)
The really unintuitive bit is that the condition is the reverse of what you would expect, so I wouldn't call it "easy to get right".
Exchange sort is more intuitive and almost as simple, and if you don't mind something a little less intuitive but still very simple, just do insertion, it is often considered the best of the simple (N^2) sorting algorithms.
For me, the most intuitive and the less likely I would get wrong would be selection. It is actually the one I came up with naturally before I even knew about sorting algorithms, it is a couple of lines longer than the others though, and often considered worse than insertion.
I had to change the order of the rows and columns of a matrix to force the diagonal to be ordered. One possibility was to use the sort function on the diagonal, somehow get the permutation, and then apply the permutation to all the rows and columns. How had can it be?
There is a 50% chance of apply the permutation in the wrong direction, and other possible tricky details.
Since the worst case was N=20, I used bubble sort that is as quick and dirty, but it's also obvious and well known.
I 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) 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...
Question 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?
The “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.
It'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.
I 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.
Well 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.
This 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.
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.
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)
I would have a hard time understanding why this finishes with the "updates" in the order expected instead of the opposite order, and I'm intrigued. In the paper it just seems to counter-intuitive to me that if the comparison is that way round then the items get swapped ... if I found this in code I was auditing then I'd spent a long time trying to work out what was going on.
Yes, not something I would write in production code. But very easy for me to think about in a stream of consciousness. Usually I complete the above challenges in about 5-10mins.
This 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
This 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?
It 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.
I 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?
Extremely 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.
Nothing 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.
This 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.
On 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.
Is 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.
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.
Feels 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.
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".
reply