Sull' ordinamento dei numeri

[curie88]

Buongiorno, credo che quasi tutti conoscano la risposta a questo quesito, ma vorrei proporlo ugualmente come gioco:
Quanti passi al minimo sono necessari per poter ordinare $100$ numeri disposti casualmente?
Se avete voglia di trascrivere pure un vostro algoritmo...

[dan95]

Con operazione intendi scambiare due numeri alla volta immagino.

Penso che la tua domanda possa essere riformulato sfruttando la teoria dei gruppi, in particolare il gruppo simmetrico $S_{100}$. Prendere una disposizione casuale dei 100 numeri equivale a prendere un elemento $\sigma \in S_{100}$ che permuta i numeri in modo da disporli nella configurazione casuale iniziale, a questo punto se chiamiamo $n$ l'ordine di $\sigma$, il numero di trasposizioni che formano $\sigma^{n-1}$ è il numero minimo delle operazioni che servono.

[curie88]

Ciao @dan95, ti ringrazio per la risposta.
Quindi se ho ben capito, il numero di scambi(stando alla teoria dei gruppi da te enunciata) necessari, o permutazioni di due qualsivoglia elementi per ottenere la configurazione ordinata, partendo da un insieme casuale, è $n-1$?
Come si può dimostrare?

[dan95]

No non ho detto che è $n-1$, ho detto che il numero di trasposizioni che formano $\sigma ^{n-1}$ che dipende dalla struttura ciclica di $\sigma$ con questo hai un algoritmo dispendioso ma funzionante

[curie88]

Ok, avevo inteso male.
Chiarisco il motivo della mia domanda: è possibile che questo numero di trasposizioni possa essere determinato in modo preciso come funzione di $n$?
Ad esempio, esiste tra i tanti algoritmi di ordinamento, più di una versione dell' algoritmo "bubblesort", che scambia due elementi alla volta, di un insieme, per poterlo ordinare.
Ho posto la domanda poiché trovo interessante il calcolo dell' efficienza degli algoritmi, sebbene non sappia quasi nulla in proposito.
In particolare mi incuriosisce sapere, quale tra i vari "bubblesort" è il più efficiente in termini di minor trasposizioni, e qual è questo numero se $n=100$?