Se ricordo giusto è un QuickSort, che in pratica è basato su pivot. Una spiegazione ben fatta anche se inizialmente ostica di questo algoritmo è su wiki: https://it.wikipedia.org/wiki/Quicksort
Se ricordo giusto è un QuickSort, che in pratica è basato su pivot. Una spiegazione ben fatta anche se inizialmente ostica di questo algoritmo è su wiki: https://it.wikipedia.org/wiki/Quicksort
Originariamente inviata da Dascos
Scusami ma così è anche più complicato.
Ultima modifica di lucas726; 08-07-2022 a 18:59
Mi riaggancio anche alla risposta di KillerWorm.
In pratica, diciamo che tu hai questi valori nell'array: 3,6,1,8,4,9,5
Diciamo che li vuoi ordinare in modo ascendente e quindi definisci la tua funzione in uno dei due modi che hai portato di esempio.
Andiamo "dietro" alla funzione usort, che usa l'algoritmo QuickSort.
Più o meno succede così...l'algoritmo usort cerca un "pivot", cioè un valore iniziale da usare poi come "paragone" e, per semplicità, facciamo finta che vada a prendere il valore finale, cioè 5. Questo 5 è "a".
Ora l'algoritmo prende uno a uno tutti i valori a sinistra e li confronta a 5 in base alla tua funzione: alla funzione arriverà quindi la coppia 5-3. Siccome 3 è inferiore (perchè così stabilisce la tua funzione di confronto), viene lasciato lì dov'è.
Poi arriva la coppia 5-6. 6 è superiore, quindi viene posizionato a destra e, internamente, l'array è diventato 3,1,8,4,9,5,6
Poi arriva 5-1 e resta così com'è. Poi 5-8 e siccome 8 è maggiore finisce a destra, e l'array è 3,1,4,9,5,6,8. Poi arriva al 5-9 e trasforma l'array in 3,1,4,5,6,8,9.
Ora procedo a cercare un nuovo pivot e l'algoritmo sceglie il 4 e lavora sulla parte a sinistra del pivot originale (quindi sui numeri 3,1, e 4). Per "sfiga" in questo ciclo resta tutto uguale. Poi passa a un nuovo pivot da scegliere nella parte sinistra dell'ultimo pivot scelto, e avendo solo due numeri alla fine sposta il 3 a destra, arrivando all'array 1,3,4,5,6,8,9....
Permessi di invio
Rispondi quotando