Finding The Median
September 11, 2015
Since there are only 256 possible values in the array, the easiest way to solve this exercise is to create an array of 256 counters, all initially zero, index through the input array incrementing the value that corresponds to the current element; when the input is exhausted two pointers approach from opposite ends of the counts
array, accumulating until the counts equal or exceed half the length of the array, when the median is calculated:
(define (median xs) (let* ((counts (make-vector 256 0)) (len (do ((xs xs (cdr xs)) (len 0 (+ len 1))) ((null? xs) len) (vector-set! counts (car xs) (+ (vector-ref counts (car xs)) 1))))) (let loop ((lo 0) (lo-count 0) (hi 255) (hi-count 0)) (cond ((< lo-count (/ len 2)) (loop (+ lo 1) (+ lo-count (vector-ref counts lo)) hi hi-count)) ((< hi-count (/ len 2)) (loop lo lo-count (- hi 1) (+ hi-count (vector-ref counts hi)))) (else (/ (+ lo hi) 2))))))
That’s clearly linear time, as it touches each item in the input once, and constant space, since the size of the counts
array is independent of the input. Here are some examples:
> (median '(2 4 5 7 3 6 1)) 4 > (median '(5 2 1 6 3 4)) 7/2
If you don’t mind scrambling the input, another algorithm that works in linear time and constant space uses a “fat pivot” quicksort, recurring only on the partition that contains the median index.
You can run the program at http://ideone.com/paTvbD.
Similar solution in Perl:
Clever! My knee-jerk reaction was to ignore the 8-bit integer part and just go for the slower generic solution.
I’ve used this as an opportunity to learn some Rust. I like that it made me think about the empty array case.
Python solution.
@graham, I think you have an “off by one error”. In the loop ‘lo’ is incremented before use, so the value of count[0] is never added to lo_count. Similarly, ‘hi’ is pre-decremented, so count[255] is never added to hi_count.
@Mike: good eye! Sorry for the errors, all.
[…] Programming Praxis problem. The problem is nicely constrained by limiting it to 8-bit […]
It looks like my solution (along with the issue @Mike caught) doesn’t correctly handle the case of a single element array. Apologies!
#!/usr/bin/perl -w
use strict;
my @array = qw/1 2 3 4 9 10 11/;
print median(@array);
sub median
{
my @vals = sort {$a $b} @_;
my $len = @vals;
if($len%2) #odd?
{
return $vals[int($len/2)];
}
else #even
{
return ($vals[int($len/2)-1] + $vals[int($len/2)])/2;
}
}
#include
int main()
{
int a[10],i,j,n;
printf(“Enter the no of events\n”);
scanf(“%d”,&n);
printf(“Input\n”);
for(i=0;i<n;i++)
scanf("%d",a+i);
for(i=1;i<n;i++)
for(j=0;ja[i])
a[j] = a[j]*a[i]/(a[i]=a[j]);
printf(“Output\n”);
for(i=0;i %d”,a[n/2]);
else
printf(“Median is -> %d”,(a[n/2]+a[n/2 -1])/2);
}