3 ms·
Count number of outer passes of insertion sort (it is N) vs bubble sort (with early exit; it is 2) if you have only a single pair misplaced.
by SomeoneFromCA 3y ago
Count number of outer passes of insertion sort (it is N) vs bubble sort (with early exit; it is 2) if you have only a single pair misplaced.
- kragen 3y agoinsertion sort only ever makes one outer pass; it does almost exactly half as many comparisons as bubble sort (n rather than 2n-2) in that case, and the same number of swaps (1) the wikipedia article has a cleverer early-exit version of bubble sort that keeps track of the last pair it had to swap; it will do 1.5n-1 comparisons in that case on average (because the swapped pair is on average in the middle of the array) above i linked to working code on godbolt (modulo the extra unnecessary swaps on duplicate keys that you were kind enough to point out earlier); edit a comparison counter and a swap counter into it and you'll see