4 ms·
Nope, bubble sort always performs the same number of ops regardless of whether the array is partially sorted or not. You might be thinking about insertion sort,
by xrisk 8y ago
Nope, bubble sort always performs the same number of ops regardless of whether the array is partially sorted or not. You might be thinking about insertion sort, which has that feature.
- JoeSmithson 8y agoBubble sort's number of operations can vary from n, if the list is sorted already, up to O(n*n) if the list is reversed.
- umanwizard 8y agoNot true. (3 2 1) -> (2 3 1) -> (2 1 3) -> (1 2 3) (3 passes, 3 swaps) Compare: (1 3 2) - > (1 2 3) (2 passes, 1 swap)
- xrisk 8y agoHmm I suppose you're right. My bad!
- ape4 8y agoIf you write it really poorly that might happen - but its easy to add a check to see if any swaps occurred. If none, you are done.