What's the fastest way to find the Kth smallest value in an unsorted list without sorting?

My initial algorithm:

• Compare element 0 with every other element, keeping track of how many elements are less than it.

• Repeat for each element until an element that is greater than exactly (k-1) elements is found.

I assume this would take $O(n^2)$ in the worst case. Can a faster runtime be achieved without sorting the list?

Unfortunately I can't just comment but I have to post it as an answer.

Anyway, you could try to use a min-heap on your unsorted array, you should be able to get a time complexity of O(n+k*logn).

StackExchange Computer Science Q#70194, answer score: 5