Understanding the median selection algorithm?

Question

Currently, I study algorithms in my free time, but when I study select () algorithms in Chapter 3, the following question is asked.

I understand that I can use the select () algorithm to find the average (n / 2nd least) if I used an array of A to n numbers.

1), but this is a bit that I am trying to understand. A = [3, 7, 5, 1, 4, 2, 6, 2]. suppose this is an array. which is the contents of the array after each call to Partition () and the parameters in each recursive call to Select ().

can someone explain how they do this?

below is the pseudo-code for 2 algorithms.

Select(A, p, r, k) { /* return k-th smallest number in A[p..r] */ if (p==r) return A[p] /* base case */ q := Partition(A,p,r) len := q – p + 1 if (k == len) return A[q] else if (k<len) return Select(A,p,q-1,k) else return Select(A,q+1,r,k-len) } 

and the second code

 Partition(A, p, r) { /* partition A[p..r] */ x := A[r] /* pivot */ i := p-1 for j := p to r-1 { if (A[j] <= x) { i++ swap(A[i], A[j]) } } swap(A[i+1], A[r]) return i+1 } 

The book I am using is called "Algorithm Derivation" by Ann Caldaway.

Answer 1

This algorithm works in two stages. The splitting step works by selecting some rotation element, and then rearranging the array elements so that everything smaller than the rotation point is on one side, larger than the rotation point, on the other hand, and the axis of rotation is in the right place. For example, given an array

 3 2 5 1 4 

If we select a bar from 3, we can split the array as follows:

 2 1 3 5 4 +--+ ^ +--+ ^ | ^ | | +--- Elements greater than 3 | +-------- 3, in the right place +------------- Elements less than 3 

Note that we did not sort the array; we just brought it closer to sorting. This, by the way, is the first step in quick sorting.

Then the algorithm uses the following logic. Suppose we want to find an element that belongs to index k in sorted order (kth smallest element). Then, depending on the point we have chosen, there are three options:

• The rod is in position k. Then, since the point is in the right place, the value we are looking for should be a bar. We are done.
• The spring is in position greater than k. Then the kth smallest element must be in the part of the array before the pivot point, so we can recursively look for this part of the array for the kth smallest element.
• The tripod is in a position less than k. Then the k-th smallest element should be somewhere in the upper region of the array, and we can return it there.

In our case, suppose we need the second smallest element (the one that is in position 2). Since the pivot point was at position 3, this means that the second smallest element must be somewhere in the first half of the array, so we will sub-recursively

 2 1 

If we needed the actual median element, since the rod fell in the middle of the array, we would simply infer that the median is 3 and it will be executed.

Finally, if we wanted something like the fourth smallest element, then, since the point is before position 4, we return it to the upper half of the array, namely

 5 4 

and will look for the first smallest element here, since there are three elements in front of this area.

The rest of the algorithm is detailed information on how to make the split step (which is probably the most requested part of the algorithm) and how to choose from three options: recursively or not (a little less complicated). Hopefully, however, this high-level structure helps the algorithm make more sense.

Hope this helps!