This page (revision-4) was last changed on 07-Mar-2017 17:13 by Albrecht Striffler

This page was created on 07-Mar-2017 14:03 by unknown

Only authorized users are allowed to rename pages.

Only authorized users are allowed to delete pages.

Page revision history

Version Date Modified Size Author Changes ... Change note
4 07-Mar-2017 17:13 1 KB Albrecht Striffler to previous
3 07-Mar-2017 17:08 1 KB Albrecht Striffler to previous | to last
2 07-Mar-2017 14:03 1 KB Albrecht Striffler to previous | to last
1 07-Mar-2017 14:03 1 KB unknown to last

Page References

Incoming links Outgoing links
FilteredMedian2 ...nobody

Version management

Difference between version and

At line 15 removed one line
At line 17 changed 4 lines
var sortedHistory = sort(valueHistory(history));
var topQuartil = sortedHistory.slice(history.length * 0.75);
var medianIndex = topQuartil.length % 2 == 0 ? (topQuartil.length / 2) - 1 : (topQuartil.length - 1) / 2
return topQuartil[medianIndex];
return computeMedian(topQuartil(history);
At line 23 changed 6 lines
function valueHistory(history) {
var valueHistory = [];
for (var i = 0; i < history.length; i++) {
valueHistory.push(history[i].value);
}
return valueHistory;
function topQuartil(history) {
return history.sort().slice(history.length * 0.75, history.length)
At line 31 changed 21 lines
function sort(history) {
return quickSort(history, 0, history.length - 1);
}
function quickSort(arr, left, right) {
var i = left;
var j = right;
var tmp;
pivotidx = (left + right) / 2;
var pivot = arr[pivotidx.toFixed()];
while (i <= j) {
while (parseInt(arr[i]) < pivot)
i++;
while (parseInt(arr[j]) > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
function computeMedian(a) {
var low = 0;
var high = a.length - 1;
var median = (low + high) / 2;
do {
if (high <= low) {
return a[median];
At line 53 changed 6 lines
}
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
return arr;
if (high == low + 1) {
if (a[low] > a[high]) {
swap(a, low, high);
}
return a[median];
}
var middle = (low + high) / 2;
if (a[middle] > a[high]) {
swap(a, middle, high);
}
if (a[low] > a[high]) {
swap(a, low, high);
}
if (a[middle] > a[low]) {
swap(a, middle, low);
}
swap(a, middle, low + 1);
var ll = low + 1;
var hh = high;
do {
do {
ll++;
} while (a[low] > a[ll]);
do {
hh--;
} while (a[hh] > a[low]);
if (hh < ll) {
break;
}
swap(a, ll, hh);
} while (true);
swap(a, low, hh);
if (hh <= median) {
low = ll;
}
if (hh >= median) {
high = hh - 1;
}
} while (true);
At line 72 added 6 lines
private static void swap(a, i1, i2) {
var temp = a[i1];
a[i1] = a[i2];
a[i2] = temp;
}