che esprime la velocità di un algoritmo di ordinamento

Question

che esprime la velocità di un algoritmo di ordinamento

#1 da (1 voti)

1

Come esprimerei la velocità del seguente algoritmo di ordinamento? So che bubblesort è n ^ n (er, intendo n ^ 2 ... come qualcuno ha sottolineato in seguito). Di seguito l'array diminuisce ogni volta che lo si chiama in modo ricorsivo.

Grazie.

$myarray = array("21","4","8","8","1","2","19","21");
mysort($myarray);

function mysort($myarray,$sorted = null){
    if(!isset($sorted)){
        $sorted = array();
    }
    $lowest = $myarray[0];
    $lowindex = 0;
    for($x = 1;$x < count($myarray);$x++){
        if($myarray[$x] < $lowest){
            $lowest = $myarray[$x];
            $lowindex = $x;
        }
    }
    $sorted[] = $lowest;
    array_splice($myarray,$lowindex,1);
    if(count($myarray) > 1){
        echo "calling recursively \n";
        mysort($myarray,$sorted);
    }
    else if(count($myarray) == 1){      
        $sorted[] = $myarray[0];
        $arraystr = print_r($sorted,true);
        echo "sorting finished. Array is $arraystr \n";
        return;
    }
}

algorithms sorting

posta nettie 25.01.2014 - 14:15

fonte

1 risposta

Leggi altre domande sui tag algorithms sorting

Implementazione di un'interfaccia da un framework vs una semplice interfaccia java In Ruby, cambia globale nel blocco sicuro thread

score 1 · Answer 1

array_splice è nella peggiore ora lineare, ma assumiamo che sia un tempo costante (se non lo è, si può scrivere quella parte in modo diverso per renderlo costante). L'algoritmo ha tuttavia la stessa complessità asintotica di Bubblesort:

Trova l'elemento più piccolo in n confronti, lo sposta in primo piano (lasciando n-1 elementi da ordinare) e ordina il resto.
Trova il secondo elemento più piccolo nei confronti di n-1, lo sposta in avanti (lasciando n-2 elementi da ordinare) e ordina il resto.
Trova il terzo elemento più piccolo nei confronti di n-2, lo sposta in primo piano (lasciando ordinati gli elementi n-3) e ordina il resto.
...

In totale, ci sono circa n + (n-1) + (n-2) + (n-3) + ... + 1 = 1 + 2 + 3 + ... + n confronti. Questo è il numero triangolare n * (n - 1) / 2, che è in Θ (n ^ 2), la stessa complessità di Bubblesort.

Non sorprendentemente, questo algoritmo è ben noto, anche se è più comunemente fatto sul posto e utilizza un ciclo invece di ricorsione. Si chiama tipo di selezione .