3 ms·
i'm not sure; i made a few mistakes in each of them as i was writing them, but they were both working by the time i first tested them. i do feel like the inser
by kragen 3y ago
i'm not sure; i made a few mistakes in each of them as i was writing them, but they were both working by the time i first tested them. i do feel like the insertion sort was maybe a little more challenging?
edited to add: someonefromca spotted a bug in the insertion sort; where it says
if (tmp > a[j-1]) break;
it should say
if (tmp >= a[j-1]) break;
which is both a performance bug and also breaks the stability property the algorithm otherwise has
this is some evidence in favor of your point that insertion sort is more error-prone; even if i could have made the same error in the bubble sort, i didn't, and possibly that was because the rest of the algorithm required less mental effort?
- abecedarius 3y agofwiw that comparison was where I went "wait, is that right?" in my reading. Maybe a fair judge of mental difficulty would say "you gotta write at least the loop invariant" (termination being too pedantically obvious) -- though admittedly I leave it out more than I used to. When I was introduced to sorting as a new programmer, via bubblesort, I thought "why that way?" and came up with selection sort as a method that made more obvious sense. It seems to me like bubblesort's alleged intuitiveness is post hoc from the shortness of the code in terms of all-ascending for-next loops -- the intuitive reason it worked was just that the inner loop did move the next max into place just like selection sort, but with extra swaps along the way.
- aristophenes 3y agoYou should edit the code in your original comment, someone is bound to copy paste the code somewhere…
- kragen 3y agoit's only editable for two hours, for better or worse