K-th smallest element

Reading time ~1 minute

Task: Given an unsorted array of integers, find the k-th smallest entry.

Solution: this can be viewed as a reduce-and-conquer problem. The key-idea is to select an element as pivot and split the array into two sub-arrays, smaller (A) and greater (B) than pivot. Then, as long the length of A is greater or equal to k, we delegate the task to this array. Otherwise, we check if the rank of the smallest entry in B is greater or equal to k in the original array (n-|B|). If so, delegate the problem to B with k’ = k-(n-|B|). Otherwise, return the pivot value.

The worst case time of this method is O(n^2), for more information see the Wikipedia article.

Software Engineering at Cxense

A year ago I wrote [a post](http://s-j.github.io/ten-things-i-wish-i-knew-before-starting-on-a-phd/) about the things I have learned duri...… Continue reading

Having fun with Scikit-Learn

Published on December 01, 2016

A few thoughts about Spark

Published on November 21, 2016