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 #include #include using namespace std; int main(){ cout<<"Enter numbers:"; int x; vectorintegers; while(cin>>x) integers.push_back(x); typedef vector::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: "<

Accepted Answer

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.

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

Solution

Problem