Devtron 168 Report post Posted August 12, 2007 Ok i need to find the Quartile of x amount of numbers now that in it self is not a problem, the problem i have is doing it effeciently say i have the numbers 4 2 1 3, in a vector, i sort them so they become 1 2 3 4 now its easy to find the middle Quartile, i can also find the first Quartile, 1.5 and 2.5, now i need the high Quartile, now here comes my problem, i dont know exatly how to do that effeciently, the only way i can think of is to resort the vector with the numbers in reverce direction, the problem is that there must be a faster way to do it. ------------------ Learning C++ 0 Share this post Link to post Share on other sites
Zahlman 1682 Report post Posted August 12, 2007 Quote:Original post by DevtronOk i need to find the Quartile of x amount of numbersnow that in it self is not a problem, the problem i have is doing it effecientlysay i have the numbers 4 2 1 3, in a vector, i sort them so they become 1 2 3 4now its easy to find the middle Quartile, i can also find the first Quartile, 1.5 and 2.5, now i need the high Quartile, now here comes my problem, i dont know exatly how to do that effeciently, the only way i can think of is to resort the vector with the numbers in reverce direction, the problem is that there must be a faster way to do it.------------------Learning C++Vectors are random-access, and asking for their .size() is constant-time (they keep track of that information). So just calculate the position where the high quartile starts, and index in. 0 Share this post Link to post Share on other sites
fpsgamer 856 Report post Posted August 12, 2007 So if I understand correctly, your question boils down to: How can I sort a std::vector of numbers in descending order?First you can include the standard <algorithm> header for access to, you guessed it: algorithms. Then tell it to sort your container, but ensure to provide it with reverse iterators pointing to the beginning and end of the vector.Example:std::vector<int> v;std::sort(v.rbegin(), v.rend());The algorithm used for the sort is implementation dependent, but its probably Quick Sort.[Edited by - fpsgamer on August 12, 2007 11:57:52 AM] 0 Share this post Link to post Share on other sites
Devtron 168 Report post Posted August 12, 2007 I have already sorted them, and i know how to find the median of x amount of numbers, my problem is locating the low and high quartile.now from what i figure i could take the size of the vector say it has 10 numbers in it and then devide that by 4, 10/4= 2.5 , then problem then becomes that the low quartile is 3 in this case and then my problem comes as there is nothing in the 2.5 spot in the vector, dose the vector just round of and say 2, if so if the number i had gotten was 2.99 had it still just rounded of at 2 ? 0 Share this post Link to post Share on other sites
TheUnbeliever 963 Report post Posted August 12, 2007 L = {1, 2, 3, 4}n = length(L) + 1 = 5L_{i} = i^{th} element of LQ_{1} = average(L_{floor(n / 4)}, L_{ceiling(n / 4)})Q_{2} = average(L_{floor(n / 2)}, L_{ceiling(n / 2)})Q_{3} = average(L_{floor(3n / 4)}, L_{ceiling(3n / 4)})(3n / 4 = (n / 4) + (n / 2))Of course, Q_{3} can be gotten in the same way as Zahlman describes -- indexing from the end rather than the beginning using the index from Q_{1}. 0 Share this post Link to post Share on other sites
Devtron 168 Report post Posted August 12, 2007 Quote:Original post by TheUnbelieverL = {1, 2, 3, 4}n = length(L) + 1 = 5L_{i} = i^{th} element of LQ_{1} = average(L_{floor(n / 4)}, L_{ceiling(n / 4)})Q_{2} = average(L_{floor(n / 2)}, L_{ceiling(n / 2)})Q_{3} = average(L_{floor(3n / 4)}, L_{ceiling(3n / 4)})(3n / 4 = (n / 4) + (n / 2))Of course, Q_{3} can be gotten in the same way as Zahlman describes -- indexing from the end rather than the beginning using the index from Q_{1}.my brain hurts i dont understand any of those formulasand i have thought about reversing the index, 0 Share this post Link to post Share on other sites
Antheus 2409 Report post Posted August 12, 2007 Quote:Original post by Devtronmy brain hurts i dont understand any of those formulasand i have thought about reversing the index,Floor and ceilingThey are provided by the cmath library in C++.Q1-Q3 are average of either one or two values, depending on the size of the array. 0 Share this post Link to post Share on other sites
Devtron 168 Report post Posted August 12, 2007 here is a question,vector<double> numbers;vector<double>::size_type size = numbers.size();if i enter 3 numbers into the vector, and i ask for how many numbers are in it it will tell me there are 3 numbers in it, now if i want to devide that by 2, as fare as i know from normal math 3/2 = 1.5, but if i do that to size/2 it returns 1, so if i understand this right asking for a vector size and deviding that it will never return a .* value but only an * value. 0 Share this post Link to post Share on other sites
TheUnbeliever 963 Report post Posted August 12, 2007 Integer arithmetic will give you an integer result. Floating point arithmetic will give a floating point result.In short:void integerArithmetic(){ int three = 3; int two = 2; int one = 1; assert(three / two == one);}void floatingArithmetic(){ double three = 3.0; double two = 2.0; double onePointFive = 1.5; assert(three / two == onePointFive);}EDIT: Also worth noting is that directly comparing floating point values is usually a bad idea. See What Every Computer Scientist Should Know About Floating-Point Arithmetic. 0 Share this post Link to post Share on other sites
Zahlman 1682 Report post Posted August 12, 2007 Quote:Original post by Devtronhere is a question,vector<double> numbers;vector<double>::size_type size = numbers.size();if i enter 3 numbers into the vector, and i ask for how many numbers are in it it will tell me there are 3 numbers in it, now if i want to devide that by 2, as fare as i know from normal math 3/2 = 1.5, but if i do that to size/2 it returns 1, so if i understand this right asking for a vector size and deviding that it will never return a .* value but only an * value.Right. Integer arithmetic in C and C++ (and many other programming languages) simply discards the remainder. If you want a floating-point result, then at least one of the inputs needs to be a floating-point value.This behaviour is actually very useful in many situations.(Also, keep in mind that the type of the indices has nothing to do with the type of the elements. 0 Share this post Link to post Share on other sites
Devtron 168 Report post Posted August 12, 2007 vector<double> numbers;vector<double>::size_type size = numbers.size();when i do this and then i take size and /2 and the ther where 3 numbers in the vector, now i made the vector double, witch as i understand is it a larget container than float, why when i devide the number 3 double with 2, dose it return a 1 instead of 1.5 then 0 Share this post Link to post Share on other sites
TheUnbeliever 963 Report post Posted August 12, 2007 Because a vector<double> contains elements of type double. However, what a vector contains (quite rightly) has no consequence whatsoever for its size_type (as Zahlman pointed out in his previous post).After all, it can only have an integral number of elements: what sense does half an element make? So size_type will always be some integer type and will need cast to double or float to get floating point results.Double isn't just a larger container than float in terms of being able to hold a larger number: it also offers a greater precision. It's worth your time to read up on how floating point numbers are represented. 0 Share this post Link to post Share on other sites
Devtron 168 Report post Posted August 12, 2007 how do i fix the errors or rather warrnings that i get when compiling the code// Write a program to compute and print the quartiles // (that is, the quarter of the numbers with the largest values, the next highest quarter, and so on) // of a set of integers.#include <iostream>#include <vector>#include <algorithm>using std::cout; using std::cin;using std::endl; using std::vector;using std::sort;int main(){ // ask for and read the numbers cout << "Enter some numbers and this program will display the quartiles" << endl << "Enter numbers: "; vector<double> numbers; double x; // invariant:numbers contains all the numbers read so fare while (cin >> x) numbers.push_back(x); // check that the user entered any numbers typedef vector<double>::size_type vec_sz; vec_sz size = numbers.size(); if (size < 3) { cout << endl << "Please enter at least 3 numbers, program terminated." << endl; return 1; } // sort the numbers in numbers sort(numbers.begin(), numbers.end()); // compute the middile quartile vec_sz mid = size/2; double median; median = size % 2 == 0 ? (numbers[mid] + numbers[mid-1]) / 2 : numbers[mid]; // compute the small quartile double LowQuar; LowQuar = 0.25 * size; // compute the high quartile double HighQuar; HighQuar = 0.75 * size; // print the results to the screen cout << endl; cout << "High Quartile: " << numbers[HighQuar] << endl; cout << "Median: " << median << endl; cout << "Low Quartile: " << numbers[LowQuar] << endl; cout << size << " " << HighQuar; return 0;}(56) : warning C4244: 'argument' : conversion from 'double' to '__w64 unsigned int', possible loss of data(58) : warning C4244: 'argument' : conversion from 'double' to '__w64 unsigned int', possible loss of data 0 Share this post Link to post Share on other sites
TheUnbeliever 963 Report post Posted August 12, 2007 Use a cast: cout << "High Quartile: " << numbers[static_cast<std::vector<double>::size_type>(HighQuar)] << endl;Also, your method of computing the quartiles Q_{1} and Q_{3} is still broken. You need to multiply by size - 1 rather than size and then take the averages (with or without early-out behaviour if it's unnecessary) like I said above. 0 Share this post Link to post Share on other sites