vkostyukov

โœจย Software Engineer at Intel. Guitar player.

๐Ÿ“… Joined in 2012

๐Ÿ”ผ 141 Karma

โœ๏ธ 18 posts

๐ŸŒ€
15 latest posts

Load

๐Ÿ‘ค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)

These are very good questions. The thing is we actually stopped at two pivots. But you can try to obtain the recurrent relation for three pivots by you own using the steps provided in the post.
๐Ÿ‘คvkostyukov๐Ÿ•‘11y๐Ÿ”ผ0๐Ÿ—จ๏ธ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