3 ms·
A few mistakes in this post IMO: 1. Note that a 3 way pivoting (partitioning or decision) is EXACTLY the same as doing two consecutive 2-way pivoting. Check bo
by susi22 13y ago
A few mistakes in this post IMO:
1. Note that a 3 way pivoting (partitioning or decision) is EXACTLY the same as doing two consecutive 2-way pivoting. Check both functions. They have the exact same # of comparisons and index calculations.
2. Note that Quicksort and Quickselect (QS) and Binarysearch (BS) are very very similar. Quicksort recurses on BOTH partitions whereas QS and BS only recurse on ONE. This is important! You don't care if your pivot in Quicksearch is a little of. You still have to do the work anyways. For QS/BS you do care a lot since the other part gets immediately discarded!
3. Where 2) implies: Quicksort is harder to get non-recursive implementation. You still have to maintain some sort of stack even for the iterative part. Whereas for QS and BS it is very very easy to do an iterative version.
Now notice how you actually worsened the runtime complexity with your new approach:
1. A standard BS discards exactly half the array. Thus, after two iterations you discarded 3/4.
2. Your new algorithm's one iteration is the same as the default BS two iterations but you only remove 2/3.
Conclusion: It makes little sense (other than having fun) to apply this to BS/QS. Though, I like the complexity analysis and the overall post.
- cma 13y agoJust thinking, won't change complexity, but it could make sense to try and always choose your pivot at the front of a cache-line when possible and then choose this added pivot at then end of the cache line. Probably would only be worth it if the elements in the array numbers or tightly packed structs, and not just pointers to some allocated object elsewhere.
- vkostyukov 13y agoI'm quite disappointed in people saying that I should have replaced recursion with iteration. That wasn't my goal - to tune a binary search algorithm. I've know the exact result of this research before writing post. I've already known that it gives you literally nothing in terms of performance. The only question I had is why is so? And I wanted to show how to combine math and complexity analysis in order to figure this out. it's not about tuning something and getting gain (in business, in performance). It's about digging into the challenging problems and finding answers (and of course - having fun). Think about why we split the input array into two equals parts? There is a nice question in Skiena's algorithms book: what would be with time complexity and algorithm itself if we split the array in two parts: 1/3 and 2/3. The best answer is for sure: "Dr. Skiena, are you simply stupid asking these questions? Just rewrite it with iterations instead and relax."