vkostyukov
โจย Software Engineer at Intel. Guitar player.
๐ Joined in 2012
๐ผ 141 Karma
โ๏ธ 18 posts
๐
15 latest posts
Load more
๐คvkostyukov๐8y๐ผ2๐จ๏ธ0
๐คvkostyukov๐10y๐ผ5๐จ๏ธ0
๐คvkostyukov๐10y๐ผ1๐จ๏ธ0
๐คvkostyukov๐11y๐ผ2๐จ๏ธ0
๐คvkostyukov๐11y๐ผ1๐จ๏ธ0
๐คvkostyukov๐11y๐ผ1๐จ๏ธ0
(Replying to PARENT post)
Having two pivots in Quicksort reduces the number of swaps (# of comparisons is the same).
๐คvkostyukov๐11y๐ผ0๐จ๏ธ0
(Replying to PARENT post)
I'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."
๐คvkostyukov๐11y๐ผ0๐จ๏ธ0
๐คvkostyukov๐11y๐ผ53๐จ๏ธ29
๐คvkostyukov๐11y๐ผ1๐จ๏ธ0
๐คvkostyukov๐12y๐ผ1๐จ๏ธ0
๐คvkostyukov๐12y๐ผ1๐จ๏ธ0
๐คvkostyukov๐12y๐ผ86๐จ๏ธ16
๐คvkostyukov๐12y๐ผ4๐จ๏ธ0
(Replying to PARENT post)