3 ms·
How do you measure progress in a quicksort?
by yen223 8y ago
How do you measure progress in a quicksort?
- ridiculous_fish 8y agoGlad you asked. The progress should be a bound on the worst case time. If you have N elements, then the initial worst case time is N^2. Say after the first partition, you are left with pieces N/3 and 2N/3; the worst case time is now (N/3)^2 + (2N/3)^2. Your progress after the first partition is the difference between the original worst case and the new worst case. This can make for uneven progress advancement but it’s monotonic: the progress bar will never go backwards.