I am trying to compute the lower quartile, median and upper quartile of a sorted STL vector of size n. One could achieve this by identifying the correct formulae for the quartiles for the 4 cases when n is (1) singly even, (2) doubly even, (3) ‘singly odd’ or (4) ‘doubly odd’ and using a nested conditional statement to compute the correct result.
If the sorted vector is v, the results are, after computing
k = n/2,
l = k/2:
// Case 1: n doubly even (n = 2*k, k = 2*l -> n = 4*l) Q1 = (v[l - 1] + v[l])/2 Q2 = (v[2*l - 1] + v[2*l])/2 Q3 = (v[3*l - 1] + v[3*l])/2
// Case 2: n 'singly odd' (n = 2*k+1, k=2*l -> n = 4*l + 1) Q1 = (v[l - 1] + v[l])/2 Q2 = v[2*l] Q3 = (v[3*l - 1] + v[3*l])/2
// case 3: n singly even (n = 2*k, k= 2*l + 1 -> n = 4*l + 2) Q1 = v[l] Q2 = (v[2*l - 1] + v[2*l])/2 Q3 = v[3*l + 1]
// case 4: n 'doubly odd' (n = 2*k + 1, k = 2*l + 1 -> n = 4*l + 3) Q1 = v[l] Q2 = v[2*l + 1] Q3 = v[3*l + 2]
where Q1, Q1 and Q3 are the lower quartile, the median and the upper quartile respectively.
By playing around with diagrams, I found the following expressions for the lower quartile and the median that work in all cases after computing
k = n/2 and
l = k/2:
// simple universal expressions for Q1 and Q2 Q1 = (v[(k-1)/2] + v[k/2])/2 Q2 = (v[(n-1)/2] + v[n/2])/2
I guessed the following form for Q3, but it doesn’t seem to work:
// erroneous expression for Q3 Q3 = (v[(3*l + 1)/2] + v[(3*l)/2])/2
so all I need is a simple expression that always works for Q3. I understand that the solution is simple with array slicing in Python, but I would like a solution that works if array slicing is unavailable.
I feel like this should be a solved problem, but I couldn’t find an answer either on stack overflow or by googling around. I would appreciate any help at all.
Source: Windows Questions C++