Computing the quartiles of a sorted array without a conditional statement

  accelerated-c++, c++, statistics, stdvector

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.

Thank-you!

Source: Windows Questions C++

LEAVE A COMMENT