3 ms·

Your step 3 is an insertion op, not a bubble op. An insertion op inserts one element into a sorted list. A bubble op bubbles the maximum (or minimum) element t

Your step 3 is an insertion op, not a bubble op. An insertion op inserts one element into a sorted list. A bubble op bubbles the maximum (or minimum) element to the end of an unsorted list.

thaumasiotes 2y ago
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.
- BoiledCabbage 2y ago
  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".
  - thaumasiotes 2y ago
    > 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.
- GrantMoyer 2y ago
  > 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.

Your step 3 is an insertion op, not a bubble op. An insertion op inserts one element into a sorted list. A bubble op bubbles the maximum (or minimum) element to the end of an unsorted list.

thaumasiotes 2y ago

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.

BoiledCabbage 2y ago
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".
- thaumasiotes 2y ago
  > 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.
GrantMoyer 2y ago
> 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.