Averages/Median: Difference between revisions

Line 1:

{{task|Probability and statistics}}Write a program to find the [[wp:Median|median]] value of a vector of floating-point numbers. The program need not handle the case where the vector is empty, but ''must'' handle the case where there are an even number of elements.

There are ~~two~~ approaches to this. One is to sort the elements, and then pick the one in the middle. Sorting would take at least O(n log n). The ~~other~~ solution is to use the [[wp:Selection algorithm|selection algorithm]] to find the median in O(n) time.

There are several approaches to this. One is to sort the elements, and then pick the one in the middle. Sorting would take at least O(n log n). Another would be to build a priority queue from the elements, and then extract half of the elements to get to the middle one(s). This would also take O(n log n). The best solution is to use the [[wp:Selection algorithm|selection algorithm]] to find the median in O(n) time.

@@ Line 1: / Line 1: @@
 {{task|Probability and statistics}}Write a program to find the [[wp:Median|median]] value of a vector of floating-point numbers. The program need not handle the case where the vector is empty, but ''must'' handle the case where there are an even number of elements.
-There are two approaches to this. One is to sort the elements, and then pick the one in the middle. Sorting would take at least O(n log n). The other solution is to use the [[wp:Selection algorithm|selection algorithm]] to find the median in O(n) time.
+There are several approaches to this. One is to sort the elements, and then pick the one in the middle. Sorting would take at least O(n log n). Another would be to build a priority queue from the elements, and then extract half of the elements to get to the middle one(s). This would also take O(n log n). The best solution is to use the [[wp:Selection algorithm|selection algorithm]] to find the median in O(n) time.
 See also: [[Mean]], [[Mode]]
@@ Line 137: / Line 137: @@
 =={{header|Java}}==
 {{works with|Java|1.5+}}
+Sorting:
 <lang java5>// Note: this function modifies the input list
 public static double median(List<Double> list){
@@ Line 144: / Line 145: @@
    }
    return list.get((list.size()-1)/2);
+}</lang>
+{{works with|Java|1.5+}}
+Using priority queue:
+<lang java5>public static double median2(List<Double> list){
+   PriorityQueue<Double> pq = new PriorityQueue<Double>(list);
+   int n = list.size();
+   for (int i = 0; i < (n-1)/2; i++)
+      pq.poll(); // discard first half
+   if (n % 2 != 0) // odd length
+      return pq.poll();
+   else
+      return (pq.poll() + pq.poll()) / 2.0;
 }</lang>