poniedziałek, 3 marca 2014

Counting sort w PowerShell

Postanowiłem zaimplementować algorytm sortowania przez zliczanie w PowerShellu. Jest to najszybszy algorytm sortowania, ale jest tylko dla licz naturalnych. Jakiś czas temu miałem projekt, w którym porównywałem szybkość działania algorytmów, ale z powodu braku czasu i zaniedbania został niestety usunięty :/ Może kiedyś utworze nowy projekt na GitHubie.


function CountingSort-Object
{
    param(
    [int[]]$in
    )
    $max = ($in | measure -Maximum).Maximum +1
    $count=@(0) * $max #initialization

    $in | %{        
        $count[$_]++   
    }

    $out=@()
    $count | % {$i=0 }{ 
        if($_ -gt 0)
        {
            $out+= (@($i) * $_)  
        }
        $i++
    }
    return $out
}

Przykład użycia jest poniżej
CountingSort-Object 11,2,5,4,5,11,0,19,0
CountingSort-Object (1..100| random -Count 10)


Tak się zastanawiam czy można dodać tablicę $out2, która będzie zawierała ilość liczb ujemnych? Wtedy możemy rozszerzyć dziedzinę z liczb naturalnych do licz całkowitych.


Brak komentarzy:

Prześlij komentarz