Bubble Sort

[axpgn]

Il "Bubble Sort" è un algoritmo che serve per riordinare una sequenza di numeri.
Partendo dall'inizio della lista, il "Bubble Sort" confronta tra loro due numeri consecutivi della sequenza e se non sono in ordine, li scambia di posto, altrimenti li lascia dov'erano.
Inizia confrontando il primo con il secondo, poi il secondo con il terzo, il terzo col quarto e così via fino alla fine della sequenza.
Se arrivato in fondo la lista non è ancora totalmente ordinata, ricomincia il giro, e lo rifà tante volte quanto necessario.

Supponiamo di avere una qualsiasi sequenza di $40$ numeri distinti.

Qual è la probabilità che il numero in ventesima posizione si ritrovi alla trentesima dopo il primo passaggio del "Bubble Sort"?



Cordialmente, Alex


P.S.: Disclaimer: in questo quesito il "Bubble Sort" funziona come ho detto io

[vict85]

Stai proponendo un problema oppure hai bisogno di aiuto?

Comunque qualche hint:

1) Nessun valore prima della 20esima posizione può essere più grande di quella nella 20esima posizione. Infatti il bubble sort manda sempre il più grande alla fine.
2) Tutti i valori nelle posizioni dalla 21esima alla 30esima sono minori di quello alla 20esima.
3) Il valore nella posizione 31esima è maggiore di quello nella 20esima.
4) Gli altri valori non contano.

[axpgn]

In questa sezione pongo problemi

[Bokonon]

$P=sum_(n=30)^40 (9!*(n-1)!*(40-n)!)/(40!*(n-30)!)=1/930$

[axpgn]

Ok, ma perché così complicato?



Cordialmente, Alex

[Bokonon]

"axpgn":
Ok, ma perché così complicato?

Bah mi è venuto così e ho lasciato la penna scrivere
Sicuramente si può risolvere con prodotti di prob. ma mi piaceva l'idea di contare i successi e vederne la curva.

[axpgn]

La mia ...

Affinché un numero tra i primi trenta termini al trentesimo posto dopo il primo passaggio deve essere il più grande fra i primi trenta altrimenti non ci arriverà mai, quindi dati che un numero vale l'altro la probabilità che quello in ventesima posizione lo sia è $1/30$.
D'altra parte se si ferma al trentesimo posto, significa che quello al trentunesimo posto è più grande di lui ovvero deve essere il maggiore tra i primi trentuno e la probabilità che lo sia è pari a $1/31$.
In conclusione, la risposta alla domanda è $1/30*1/31=1/930$

Cordialmente, Alex