Quickselect is linear-time on average, but it can require quadratic time with poor pivot choices.
The median-of-medians algorithm does not actually compute the exact median, but computes an approximate median, namely a point that is guaranteed to be between the 30th and 70th percentiles (in the middle 4 deciles).