Determine the third quartile from a collection of integers in C++?

Question

I'm reading Accelerated C++. At the moment I'm at the end of chapter 3 and here's the exercise that I'm trying to do:

"Write a program to compute and print the quartiles of a set of integers."

I found the first and the second quartiles, but I have no idea how to find the third. Here's my code:

 #include <algorithm>
 #include <iostream>
 #include <vector>
 using namespace std;

 int main(){
    cout<<"Enter numbers:";
    int x;
    vector<int>integers;
    while(cin>>x)
        integers.push_back(x);

    typedef vector<int>::size_type vec_sz;
    vec_sz size = integers.size();
    sort(integers.begin(), integers.end());
    vec_sz mid = size/2;
    vec_sz q1 = mid/2;
    double median;
    median = size % 2 == 0 ? ((double)integers[mid] + (double)integers[mid-1]) / 2
: integers[mid];
    double quartOne = ((double)integers[q1] + (double)integers[q1-1])/2; 
    cout<<"The First Quartile is: "<<quartOne<<endl;
    cout<<"The Second Quartile is: "<<median<<endl;
    return 0;
}

I don't know why you think the first quartile is always an unweighted average of two items. — Ben Voigt, May 26 '12 at 21:06

Andrew Tomazos · Accepted Answer · 2012-05-26T21:22:57.377

3

One way would be to sort the collection and then take the 3 dividing items:

vector<int> v = ...;
sort(v.begin(), v.end());
int q12 = v[v.size()*1/4];
int q23 = v[v.size()*2/4];
int q34 = v[v.size()*3/4];

This is O(nlogn) in the number of data items.

Another way would be to perform a binary search of the data for the three divisions seperately. ie propose an initial q12, check if it is correct by making a pass of the data, if it is incorrect adjust it up or down by half, and repeat. Do likewise for q23 and q34.

This is technically O(n) because a 32-bit int has a fixed range and can be binary searched in 32 passes max.

edited May 26 '12 at 21:22

answered May 26 '12 at 21:17

Andrew Tomazos

66,139
40
186
319

that's it. i got it after the first answer but it's author decided to delete it so i'm awarding you. thanks. :) – Windom Earle May 26 '12 at 21:23
2

This is wrong. What if the vector has an even number of elements? Median (or second quartile) is then supposed to be the mean of the two central values. – betabandido May 26 '12 at 21:24
I'm checking for this here: "median = size % 2 == 0 ? ((double)integers[mid] + (double)integers[mid-1]) / 2 : integers[mid]; " – Windom Earle May 26 '12 at 21:27
I was assuming v.size is large. In the case you mention it is quite an easy adjustment. – Andrew Tomazos May 26 '12 at 21:27
@WindomEarle you need to do the check for q1 and q3 too. Have a look at the wikipedia link that I post in my answer for the correct way to compute the quartiles. – betabandido May 26 '12 at 22:33

betabandido · Answer 2 · 2012-05-26T22:52:03.067

This solutions implements the second method described in wikipedia for computing quartiles. It provides the correct values both for vectors with odd and even lengths.

#include <vector>
#include <tuple>
#include <iostream>
using namespace std;

double median(vector<double>::const_iterator begin,
              vector<double>::const_iterator end) {
    int len = end - begin;
    auto it = begin + len / 2;
    double m = *it;
    if ((len % 2) == 0) m = (m + *(--it)) / 2;
    return m;
}

tuple<double, double, double> quartiles(const vector<double>& v) {
    auto it_second_half = v.cbegin() + v.size() / 2;
    auto it_first_half = it_second_half;
    if ((v.size() % 2) == 0) --it_first_half;

    double q1 = median(v.begin(), it_first_half);
    double q2 = median(v.begin(), v.end());
    double q3 = median(it_second_half, v.end());
    return make_tuple(q1, q2, q3);
}

int main() {
    vector<double> v = {2, 2, 3, 4, 4, 5, 5, 10};
    auto q = quartiles(v);
    cout << get<0>(q) << "," << get<1>(q) << "," << get<2>(q) << endl;
    return 0;
}

It is designed for real numbers, but it is easily adaptable for integer values (just round the values to their nearest integer).

Determine the third quartile from a collection of integers in C++?

2 Answers2