Ordimanto array grosse dimensioni non intero

[ohi]

Ciao avrei bisogno di un consiglio, devo ordinare 2 array(interi) di grosse dimensioni in ordine decrescente ad esempio >50000 in base al loro rapporto A/B, quale algoritmo di consigliate?

il Bucket sort può essere adattato per valori non interi?
http://it.wikipedia.org/wiki/Bucket_sort

[:.Blizzard.:]

Puoi spiegare meglio con un esempio pratico?

Così cerchiamo di trovare la soluzione migliore.

[ohi]

Ho 2 array molto grandi:

int a[50000]
int b[50000]

e devono essere ordinati in ordine decrescente in base al rapporto a[i]/b[i]

ad esempio

a={15 11 30 36}
b={ 6 5 9 12}

15/6=2,5
11/5=2,2
30/9=3,3
36/12=3

per cui l'ordinamento finale:

a={30 36 15 11}
b={ 9 12 6 5}

[Dânêl]

per quanto ricordo dal corso di algoritmi il bucket sort richiede una distribuzione uniforme dei valori (confermato anche dalla pagina di wikipedia).

Cosi su due piedi non mi vengono molte idee.
Potresti creare una funzione di hash basata sul valore del rapporto, gestendo opportunamente le collisioni, ottenendo cosi la posizione nell'array in tempo lineare (anche se più che un array ordinato ti converrebbe usare una lista ordinata)

[wingman87]

Quicksort?

[ohi]

Avevo provato con un mergesort che come il quick sort ha coplessità media Θ(nlogn). Visto però le grosse dimensioni sarebbe ottimo adattare un algoritmo con complessità Θ(n+k)

[rеpne scasb]

■

[bobbytre]

in PHP il tuo problema si puo risolvere cosi:

function comp_decre($a, $b)
{
return ($a["key"] == $b["key"])?0:($a["key"] <$b["key"]) ? 1 : -1;
}


$a = array(15,11,30,36);
$b = array( 6,5,9,12);

for($i=0;$i<count($a);$i++)
{
$tmp[$i]['a'] = $a[$i];
$tmp[$i]['b'] = $b[$i];
$tmp[$i]['key'] =$a[$i]/$b[$i];
}

usort($tmp, "comp_decre");
$a = array();
$b = array();
for($i=0;$i<count($tmp);$i++)
{
$a[] = $tmp[$i]['a'];
$b[] = $tmp[$i]['b'];
}

print_r($a);
print_r($b);