each group in quick Select algorithm should be sort?

Answer 1

If all you need is the Median, then sorting it first could be more expensive than simply running a half-version of a selection sort, depending on your sort algorithm. In an array of n elements, you know the median will be the middle (n/2+1) element if n is odd, or the average of the two middle elements (n/2, n/2+1) if even. So perform a normal selection sort, but instead of running the entire O(N) operation, run it only halfway to obtain that selected median value.

You could also do the very easy Bubble Sort, but only run it n/2 times. This will ensure the median is in the middle, and is conceptually easy. Do it manually on paper if you doubt it.

Answer 2

The median is the floor(n / 2) + 1th smallest element in sorted order, which the selection algorithm can find in O(n) (considering n to be odd for convenience). So if you know that all the elements to the left of k are smaller than k and all the ones to the right are bigger than k and k is in position floor(n / 2) + 1, then you know that k is the median. You don't need to sort.

For example:

8 3 11 20 18 => 11 is the median because it's in the middle and smaller than everything after it and bigger than everything before it. No sorting required.

There are many variants of the selection algorithm. The basic idea is the same for all of them, but some details might be different. Post your teacher's implementation and try to clarify your question if you need more localized help.