4 ms·
quicksort is O(n^2) which is definitely not the "best big-O" for sorting.
by sonoffett 10y ago
quicksort is O(n^2) which is definitely not the "best big-O" for sorting.
- pkaye 10y agoQuicksort is O(n log n) average and O(n^2) worst case. Heapsort is O(n log n) for both average and worst case.
- sonoffett 10y ago"how do you count the bits most efficiently?" What does this even mean?
- UK-AL 10y agoWhat i think he means is counting the amount of set(1) bits in the array,
- sonoffett 10y agoThanks, the question makes more sense now :)
- dekhn 10y agoIf you have a collection of data, and you want to know the number of 1 bits, and you want to do it with a minimum of resources... what is the process? For example, standard bit-shifting and masking the lowest bit to set a counter is one way to do this. Possibly there are other, faster ways, such as using a lookup table (a byte or more can be "counted" at a time). Of course, because so many people were doing this, intel added a popcnt instruction which probably is more efficient (faster) than either of the above, at the expense of more CPU real estate, heat, etc. Turns out counting 1 bits in a dataset is a super-important problem that shows up in a lot of situations.
- Jiig 10y agoIts worst case is O(n^2) sure, so heap sort would be better if you know that your data would hit the worst case scenario of quick sort every time.
- dekhn 10y agoquicksort is O(nlogn) average case, and O(n2) on already sorted arrays.
- bvinc 10y agoJust a nitpick: There are versions of quicksort that perform well, O(n*log n), on already sorted data. But there is always some worst case scenario where it can be O(n^2).