How to resolve the algorithm Averages/Median step by step in the F# programming language

Published on 12 May 2024 09:40 PM
#F_Sharp

How to resolve the algorithm Averages/Median step by step in the F# programming language

Table of Contents

Problem Statement

Write a program to find the   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.   In that case, return the average of the two middle values. There are several approaches to this.   One is to sort the elements, and then pick the element(s) in the middle. Sorting would take at least   O(n logn).   Another approach would be to build a priority queue from the elements, and then extract half of the elements to get to the middle element(s).   This would also take   O(n logn).   The best solution is to use the   selection algorithm   to find the median in   O(n)   time. Quickselect_algorithm

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Averages/Median step by step in the F# programming language

Source code in the fsharp programming language

let rec splitToFives list = 
    match list with
        | a::b::c::d::e::tail ->
            ([a;b;c;d;e])::(splitToFives tail)
        | [] -> []
        | _ -> 
                let left = 5 - List.length (list)
                let last = List.append list (List.init left (fun _ -> System.Double.PositiveInfinity) )
                in [last]

let medianFromFives =
    List.map ( fun (i:float list) ->
        List.nth (List.sort i) 2 ) 

let start l = 
    let rec magicFives list k =
        if List.length(list) <= 10 then
            List.nth (List.sort list) (k-1)
        else
            let s = splitToFives list
            let M = medianFromFives s
            let m = magicFives M (int(System.Math.Ceiling((float(List.length M))/2.)))
            let (ll,lg) = List.partition ( fun i -> i < m ) list
            let (le,lg) = List.partition ( fun i -> i = m ) lg
            in
               if (List.length ll >= k) then 
                    magicFives ll k
               else if (List.length ll + List.length le >= k ) then m
               else
                    magicFives lg (k-(List.length ll)-(List.length le))
    in
        let len = List.length l in
        if (len % 2 = 1) then
            magicFives l ((len+1)/2)
        else
            let a = magicFives l (len/2)
            let b = magicFives l ((len/2)+1)
            in (a+b)/2.


let z = [1.;5.;2.;8.;7.;2.]
start z
let z' = [1.;5.;2.;8.;7.]
start z'

You may also check:How to resolve the algorithm Loops/Break step by step in the ALGOL 68 programming language
You may also check:How to resolve the algorithm SHA-1 step by step in the Kotlin programming language
You may also check:How to resolve the algorithm GUI component interaction step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm Comma quibbling step by step in the zkl programming language
You may also check:How to resolve the algorithm Determine if a string has all unique characters step by step in the Fortran programming language