How to find kth smallest integer in an unsorted array without sorting the array?

Sephy, I'm going to walk this through very carefully. You always have to be careful when helping people with algorithms, because, and I cannot stress this enough, solving algorithm problems are to programmers what weight-lifting is to professional athletes. Knowing how to put yourself into the mode of thinking like a computer is what you will get paid to do in a few years. So if the solutions are just given to you, you're going to be the guy that bounces from job to job every 6 months instead of the guy who becomes the lead developer, or goes out on his own with a successful company.

Now that that rant is out of the way...

Traditionally, we think of algorithms that loop through the array once, and loop through it differently based on the first result, and repeat until we met some condition, to be O(n^2). Things that meet this criteria are selection sort, insertion sort, and bubble sort.

But it doesn't have to be. If we can properly divide the array into segments and prove the size of those segments, we can keep it on a low order.

And, with most divide and conquer algorithms, we can start in the middle.

Let A be an array of size N with N distinct elements in it.

Let M be the element that resides at A[N/2]

Let A-large be an array of all elements greater than M.
Let A-small be an array of all elements less than M.

What do we know about A-small and A large? Are they the same size? Maybe, but probably not.

Is size(A-small) > k? or is it < k?

If size(A-small) == k - 1, wouldn't that make M the kth smallest element?

Is there something we can do to create a new value for k and do some recurrsion here?

I'm not going to finish this for you, because there should be plenty to chew on. These are the questions you need to ask yourself. @templatetypedef is 100% on the right track, this is just expanding on it.

If you have some more questions, ask them, but there should be enough here to allow you to solve it without robbing you of your mental exercise.

As a hint, think about how the quicksort partition step works. It splits the input up so that the pivot is in its final position, smallest elements are to the left, and larger elements are to the right. Given this information, and knowing what index you were trying to find, could you think of a way to recursively find the kth element?