Median of 5 without sorting

I'm working on a quicksort class, but I'm required to get the pivot multiple ways (last value, median of 3, and median of 5). Getting the median of 3 is easy enough with a few if statements, but I'm having trouble figuring out how to get a median of 5 in the most efficient manner. We're timing the quicksort, so the more efficient the method of finding the median of 5, the better.
I've looked around quite a bit, and many of the ways of doing this involves sorting the array first, which is not what I want it to do. Any ideas of how to do this?

P.S. I'm not necessarily asking for code, although it would be useful. Just a proper approach would be fine.

[Taywin]

If you want to not using sort which could usually be O(nlogn) and you can use as much memory as you want, you may consider to use Hashmap to count (using the element value as Key and value of the Key is the counter). This would reduce the time to O(n). Though, I am not sure whether or not you would stop to check right away after you have found the first median of 5 or you need the highest?

By the way, you could incorporate the search for median of 5 in any previous process (going through each element in your array) you are doing to speed up your program.

[JamesCherrill]

I haven't tried this, but it may contain the seed of as useful idea?

Find the highest and lowest value (1 loop, 1 pass) - note the indexes of those values
Repeat, but skipping the highest/lowest elements - this notes the second highest and second lowest
The remaining element is the median