C#: I have an large integer array and would like to quickly calculate quartile values

Question

0.00/5 (No votes)

See more:

I would like an efficient and non-invasive way of finding a median of a large array (a double array of size 300,000).

What I have tried:

I have tried an inefficient method:

double Median(double[] xs) {
  Array.Sort(xs);
  return xs[xs.Length / 2];
}

This sorts the original array which I don't want to have happen.

Posted 9-Dec-21 12:30pm

Admin BTA

Updated 9-Dec-21 22:00pm

Add a Solution

Comments

[no name] 9-Dec-21 19:32pm

Since you have an "even" number of values, you will need "two" middle values to calculate the median.

Admin BTA 9-Dec-21 20:09pm

Good point Gerry! I intended the size to be exemplary, it could be changing in real-time: sometimes even, sometimes odd. Since this method will be called often, I need it to be as efficient as possible.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Dave Kreskowiak · Answer 1 · 2021-12-09T13:31:00

Solution 1

You don't have a choice here. Median values, by definition, require an ordered set to find them.

Posted 9-Dec-21 13:31pm

Dave Kreskowiak

Comments

Admin BTA 9-Dec-21 20:18pm

Good point, Dave. With that said, I suppose the question is what is the most efficient way of sorting.

Dave Kreskowiak 9-Dec-21 20:33pm

You're not going to do much better than the QuickSort and HeapSort algorithms Array.Sort already uses. Both use the IComparable interface to compare values though. This adds a bit of overhead to the algorithm, making it take a little bit longer.

You could implement your own QuickSort algorithm that doesn't depend on IComparable, but don't expect huge performance gains. We're talking about a few seconds better performance at best.

Admin BTA 9-Dec-21 22:08pm

in my application, 7000 ticks can make a difference, so seconds could be a huge performance gain. good thought on the quicksort. thanks.

BillWoodruff · Answer 2 · 2021-12-09T22:00:00

Solution 2

You could use the 'Median method in the open-source Math.NET Numerics library: [^].

For an interesting idea for an O(n) algorithm: [^] ... note: i have not used it.

Posted 9-Dec-21 22:00pm

BillWoodruff