2 ms·
Algorithm: Pick two elements at random. If they are out of order, swap them. Could check every n-1 steps to see whether array is sorted. Expected running time
by amichail 17y ago
Algorithm: Pick two elements at random. If they are out of order, swap them. Could check every n-1 steps to see whether array is sorted.
Expected running time is O(n^2 log(n)).
See Section 3.
- jibiki 17y agoYes, they get their bound by counting inversions. This is much better than the method I suggested in the other thread (which, of course, doesn't actually work.)