[Pseudo-Contest] Mosse per ordinare un array

[Ryuzaki_Eru]

Originariamente inviato da DanieleC88

Ovvio, ma immagina che siano i nodi di una lista, e non gli elementi di un'array. La cosa diventa fattibilissima.
Non c'è nessuno "scorrimento", nella pratica, ma l'effetto è quello.

Ma anche se non lo immagina come una lista l'effetto è quello. Nella pratica non avvine ovviamente, ma concettualmente si.

Comunque, Ryuzaki_Eri, dicci se la soluzione è esatta, se è sbagliata, o almeno dacci un indizio.

Non ho la soluzione, ma la mia era pure 9 come *minimo* numero di spostamenti per ordinare l'array.

Mi sembrerebbe strano o l'avrebbero chiamata lista. Boh

Non soffermarti troppo sui nomi. In Python si chiama lista, in C si chiama array di interi. Il concetto è quello.

Cmq c'è anche da chiarire il punto "puoi scegliere un qualsiasi elemento e spostarlo in cima o in fondo". Io lo capisco in modo vincolante, poi boh.

Non c'è niente di vincolante. Hai questo elementi e puoi sceglierne uno qualsiasi e spostarlo o in testa o in coda.

Appena ho tempo, correggo quel codice e mostro i passaggi dell'algoritmo punto per punto.

Bene, sono curioso.

[cionci]

Originariamente inviato da Ryuzaki_Eru

Non soffermarti troppo sui nomi. In Python si chiama lista, in C si chiama array di interi. Il concetto è quello.

Tra l'altro se fosse una lista, gli spostamenti sono sì gratuiti, ma lo spostamento di un elemento interno alla lista in testa ha un costo nel worst case pari ad O(N) per la ricerca delel'elemento (anche se mediamente è N/2), stessa cosa se si fa il cosiddetto "scorrimento" dell'array (in questo caso il costo è sempre O(N)).
Quindi in definitiva, per lo "scorrimento" che si tratti di un array o di una lista, il costo computazionale è sempre O(N)

[DanieleC88]

Originariamente inviato da cionci

Tra l'altro se fosse una lista, gli spostamenti sono sì gratuiti, ma lo spostamento di un elemento interno alla lista in testa obbliga ha un costo nel worst case pari ad O(N) per la ricerca delel'elemento (anche se mediamente è N/2), stessa cosa se si fa il cosiddetto "scorrimento" dell'array (in questo caso il costo è sempre O(N)).
Quindi in definitiva, per lo "scorrimento" che si tratti di un array o di una lista, il costo computazionale è sempre O(N)

Sì, ma il "contest" chiedeva appunto quanti fossero gli spostamenti minimi necessari all'ordinamento della lista/array, non si chiedeva quale fosse la complessità asintotica richiesta per farlo.

ciao

P.S.: Ryuzaki_Eri, hai raggiunto 666 post, io mi fermerei lì.

[Ryuzaki_Eru]

E me lo dici solo ora?? Ecco perchè oggi è stata una giornata d'inferno

Originariamente inviato da cionci

Tra l'altro se fosse una lista, gli spostamenti sono sì gratuiti, ma lo spostamento di un elemento interno alla lista in testa ha un costo nel worst case pari ad O(N) per la ricerca delel'elemento (anche se mediamente è N/2), stessa cosa se si fa il cosiddetto "scorrimento" dell'array (in questo caso il costo è sempre O(N)).
Quindi in definitiva, per lo "scorrimento" che si tratti di un array o di una lista, il costo computazionale è sempre O(N)

Per le liste si, lo spostamento in testa al caso peggiore è O(n), però per l'array il concetto è diverso. Certo, potrebbe essere visto come uno scambio e costerebbe sempre O(n), ma al nostro esercizio non frega nulla della complessità

[nalsk]

Ragazzi, dalla traccia dell'esercizio si capisce benissimo che la soluzione è indipendente dai passaggi "fisici" che gli elementi devono subire. Come precisato dalla traccia, una mossa comprende sia la scelta arbitraria dell'elemento sia il suo riposizionamento con annesso scorrimento degli altri elementi. Ovviamente se si va a vedere una possibile implementazione le operazioni da compiersi sono molto più di quelle che ci si aspetta.

[Ryuzaki_Eru]

Originariamente inviato da nalsk

Ragazzi, dalla traccia dell'esercizio si capisce benissimo che la soluzione è indipendente dai passaggi "fisici" che gli elementi devono subire. Come precisato dalla traccia, una mossa comprende sia la scelta arbitraria dell'elemento sia il suo riposizionamento con annesso scorrimento degli altri elementi. Ovviamente se si va a vedere una possibile implementazione le operazioni da compiersi sono molto più di quelle che ci si aspetta.

Appunto, stiamo dicendo proprio questo.