4 ms·
make a linear pass through the data, if they are in order quit, otherwise swap two random entries and repeat
by Taniwha 8y ago
make a linear pass through the data, if they are in order quit, otherwise swap two random entries and repeat
- martin_a 8y agoSo, the minimum running time for this would be O(1), but can one estimate the maximum? I don't see how, but maybe I'm missing something.
- astrobe_ 8y agoThis is known as BoZosort [1], which is said to be O(n!) on average. [1] https://en.wikipedia.org/wiki/Bogosort https://en.wikipedia.org/wiki/Bogosort
- kevinwang 8y agoI think it may be another factor of n slower than that Edit: wow nevermind, I just read the paper linked to bozo sort in wikipedia. They conjecture that it's O(n!) whereas bogosort is Omega(n*n!). Wow, that's surprising!