We're going to iterate and find a third algorithm, Let's go through our arsenal of sorting algorithms, what else is useful? We have an interesting sorting algorithm from Quick sort where we use a pivot and we recursively sort different parts of the array based on partitioning the array into the smaller than the pivot and larger than the pivot.
We can recognize that sorting is useful for solving our new problem. Maybe we can modify a sorting algorithm and design a new algorithm that's useful for the current problem. The problem of finding the k'ths smallest element.
So what if we picked a pivot in our elements, in our array of elements and thought through what happens when we sort the, not sort, partition the array into the elements that are smaller than the pivot and those that are bigger than the pivot. Now, we're not looking for fully sorted array at the end of this procedure, what we want is the k'ths smallest element.
What's useful here is that if we partition the array into those that are smaller than the pivot and those bigger than the pivot, than if we only have say three elements that are smaller than the pivot. Then the third smallest element over all is going to be the maximum of those three elements because the pivot's going to be bigger and all of the other elements in the array are going to be bigger than those bottom three elements.
So they're not going to be the third smallest and so the beauty of this approach is going to be that we only need to recursively look at only roughly half of the elements each time if we're lucky with our choice of pivot. And so what we can do is at each stage pick some random element of the array. Partition the array into those elements that are smaller than the pivot, those elements that are bigger than the pivot. And then look at the size of the set of elements, is it smaller than the pivot and compare that size to the ring.
Because that size of that set is going to tell us whether the k'th smallest element belongs in that set of elements that are smaller than the pivot, or maybe that k'th smallest element is the pivot. Or maybe that case smallest element is bigger than the pivot and so we need to look in the rest of the elements in the array.
We can code this strategy and notice that this is going to be a recursive method. It's great if we can come up with a recursive solution to our problem strategy. We're demonstrating yet another skill in programming and algorithmic development in our interview, we're demonstrating our breadth of knowledge. As we go through this recursive function development, it's going to be very important to test the code, which is why we had that base example that we can keep tracing through.
Now as we develop this new strategy, we still want to think about performance. The performance is going to depend on the fact that when we compare to the pivot at each recursive function call. We hope that we're going to divide our array of elements into the smaller thans and the bigger thans and those are going to be hopefully, roughly the same size to one another and so we get to reduce our problem size exponentially by reducing the array size in half each time.
We're hoping for on average at least, linear time. A careful analysis of the recursive performance of that function would get us at its expected on time. Now in an interview situation this might seem a little daunting to come up with such an elaborate algorithm and to do its performance analysis. But we need to keep improving the solution.
We never want to be content with the solution that we have at hand. And so when we do have a solution, it's important to think about, does it match the assumptions that we made at the beginning? How will we change it if we had different assumptions? If for example, repeated elements are allowed in the array, what do we have to do differently in our logic? We want to consider performance every time we come up with a new problem solving strategy. Have we made progress or not? Are we coming up with better solutions or are we coming up with just different solutions? Are there tradeoffs for time versus memory?
Think of ways that we can bring in our tools. What we want to do is through our practice, have a wide array of tools that we can apply to new problems.
And when we are approaching a new problem, if we've practiced a lot, we can go through a mental checklist of all the useful data structures and all of the known algorithms that we've worked through. This can help us solve the new problem using what we've done before.
