[Pseudo-Contest] Mosse per ordinare un array

[Ryuzaki_Eru]

Non sono potuto andare alla PyCon, ma ho visto che il kit comprendeva anche questo problemino:

quale è il minor numero di mosse per ordinare questo array se ad ogni mossa puoi scegliere un qualsiasi elemento e spostarlo in cima o in fondo?

[58, 29, 97, 12, 70, 30, 16, 99, 24, 33, 69, 98, 35, 47, 52]

Buon divertimento!

[nalsk]

se ho capito bene ogni elemento prelevato fa traslare gli elementi compresi nell'intervallo dalla sua vecchia posizione alla nuova, se si scelgono gli elementi dal massimo al minimo e li si posizionano sempre in testa sono n mosse per avere l'array ordinato. Gli elementi sono 15 quindi 15 mosse.

[Ryuzaki_Eru]

Quando prelevi un elemento non viene traslato nulla, semplicemente gli elementi che vengono dopo o prima l'elemento che prelevi, "scorrono".
Appena tu sposti n/2 elementi, facendo come dici tu, troverai nell'intervallo [0, n/2] i primi n/2 elementi maggiori. Quelli restanti sono i più piccoli e non è detto che devi rispostarli tutti.

[wingman87]

Credo che la soluzione sia trovare la sequenza più lunga di numeri già ordinati tra loro con la restrizione che non possono esserci numeri compresi nei limiti della sequenza all'infuori della sequenza stessa, poi prendere tutti gli altri e spostarli in cima o in fondo similmente a quanto descritto da nalsk.

EDIT:
secondo questo ragionamento la sequenza più lunga è:
29
30
33
35
47
52
Quindi abbiamo 6 numeri già al loro posto, bastano 9 mosse per portare tutti gli altri al posto giusto prima o dopo questa sequenza.

[nalsk]

quoto wingman87

cmq per traslare intendevo proprio lo slittamento, perchè un'altro metodo sarebbe la sostituzione dell'elemento scelto con quello in capo o in coda.
giusto per precisare

[Ryuzaki_Eru]

Se sposti e sostituisci alla fine fai due spostamenti

[wingman87]

Originariamente inviato da Ryuzaki_Eru

Se sposti e sostituisci alla fine fai due spostamenti

Non ho capito

[Ryuzaki_Eru]

Non mi riferivo a te.

[B|4KWH|T3]

Originariamente inviato da Ryuzaki_Eru

Quando prelevi un elemento non viene traslato nulla, semplicemente gli elementi che vengono dopo o prima l'elemento che prelevi, "scorrono".
Appena tu sposti n/2 elementi, facendo come dici tu, troverai nell'intervallo [0, n/2] i primi n/2 elementi maggiori. Quelli restanti sono i più piccoli e non è detto che devi rispostarli tutti.

Per come capisco io l'esercizio non c'è nessuno scorrimento

[DanieleC88]

Anche a me vengono 9 mosse, perché se parti da:

[58, 29, 97, 12, 70, 30, 16, 99, 24, 33, 69, 98, 35, 47, 52]

allora puoi spostare in testa alla lista, nell'ordine, il 24, il 16 e il 12, ottenendo:

[12, 16, 24, 58, 29, 97, 70, 30, 99, 33, 69, 98, 35, 47, 52]

a quel punto si possono prendere tutti i numeri che finirebbero dopo il 52 (nell'ordine: 58, 69, 70, 97, 98, 99) e spostarli ordinatamente in coda:

[12, 16, 24, 29, 30, 33, 35, 47, 52, 58, 69, 70, 97, 98, 99]

per un totale di, appunto, 9 mosse.

[Ryuzaki_Eru]

Originariamente inviato da B|4KWH|T3

Per come capisco io l'esercizio non c'è nessuno scorrimento

Come no? Quando sposti un elemento quelli che sono successivi scorrono di una posizione.

[B|4KWH|T3]

Non ci può essere scorrimento, lo scorrimento implica uno spostamento non consentito. (tra l'altro teoricamente è anche sbagliato il fatto di contare solo 9 mosse, dato che ogni spostamento alla posizione i+1 è una mossa).

Questa è la mia versione, non ho ancora ben capito la complessità che viene fuori. L'ordinamento è stabile. Probabilmente fa esteticamente schifo, ma non sono un programmatore.

Strumenti: pennarello, lavagna e pseudocodice.

Stupid-Counting-Sort(A):
   p <- 1
   c <- Count(A,p)
   while TRUE:
      if c+1>p:                                  // Se è nella posizione sbagliata, allora spostalo
         Swap(A[p],A[c+1])
         c <- Count(A,1)
      else:
         while c+1=p:                           // Se è nella posizione giusta cerca uno nella posizione sbagliata
            p <- p+1
            c <- Count(A,p)
            if c+1!=p:
               Swap(A[1],A[p])


Questa funzione conta quanti numeri ci sono inferiori al numero i per calcolare la posizione i in cui spostare il numero.
Count(A,i):
   c <- 0:
   if A[1]<A[i]:
      c <- c+1
  return c

E' una modifica del counting sort.
Il concetto è semplicemente di controllare quanti numeri c minori del numero pivot ci sono nell'array e poi scambiare la posizione del numero pivot, con la posizione c+1.
In questo caso il pivot può essere solo la posizione 1 (come nello pseudocodice) o la posizione N.

L'algoritmo si semplificherebbe molto se si potesse usare un secondo array in cui memorizzare quanti numeri ci sono minori del numero i

[B|4KWH|T3]

Originariamente inviato da Ryuzaki_Eru

Come no? Quando sposti un elemento quelli che sono successivi scorrono di una posizione.

E fai tante mosse quanti scorrimenti fai.
La traccia dice che si può fare uno Swap solo con la posizione i e con la posizione N

[B|4KWH|T3]

E poi mi sembrerebbe troppo stupido come esercizio con lo scorrimento

[Ryuzaki_Eru]

Ti stai focalizzando troppo su questo scorrimento, non hai capito di cosa sto parlando. Se hai [1,2,3] e sposti l'1 in fondo, i restanti elementi "scorrono" di una posizione. Il 2 prende il posto dell'1 e il 3 prende il posto del 2. Questo è lo scorrimento e non c'entra niente con lo spostamento di un elemento.
Il tuo algoritmo non l'ho guardato, ma mi sembra inutilmente complicato. Basta fare come è stato già detto precedentemente. Inoltre la funzione Count mi sembra sbagliata, restituisce al massimo c = 1, fa solo un controllo condizionale.

L'algoritmo si semplificherebbe molto se si potesse usare un secondo array in cui memorizzare quanti numeri ci sono minori del numero i

Allora, tralasciando un attimo il testo dell'esercizio, usa un secondo array e poi posta lo pseudocodice e l'esecuzione dell'algoritmo sull'array dell'esercizio.

[B|4KWH|T3]

Originariamente inviato da Ryuzaki_Eru

Ti stai focalizzando troppo su questo scorrimento, non hai capito di cosa sto parlando. Se hai [1,2,3] e sposti l'1 in fondo, i restanti elementi "scorrono" di una posizione. Il 2 prende il posto dell'1 e il 3 prende il posto del 2. Questo è lo scorrimento e non c'entra niente con lo spostamento di un elemento.

No.
Se in un array di n elementi devo spostare l'elemento i in posizione 1, devo spostare tutti gli elementi da 1 ad i-1 di una posizione in avanti.

Il tuo algoritmo non l'ho guardato, ma mi sembra inutilmente complicato. Basta fare come è stato già detto precedentemente. Inoltre la funzione Count mi sembra sbagliata, restituisce al massimo c = 1, fa solo un controllo condizionale.

Sì la funzione Count è sbagliata perchè manca un for.

Allora, tralasciando un attimo il testo dell'esercizio, usa un secondo array e poi posta lo pseudocodice e l'esecuzione dell'algoritmo sull'array dell'esercizio.

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

[DanieleC88]

Originariamente inviato da B|4KWH|T3

No.
Se in un array di n elementi devo spostare l'elemento i in posizione 1, devo spostare tutti gli elementi da 1 ad i-1 di una posizione in avanti.

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.

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

[B|4KWH|T3]

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.

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

Ovvio, ma c'è scritto che è un array

[DanieleC88]

Trattandosi di PyCon penso che fosse proprio una lista (non esiste un tipo "array" vero e proprio in Python).

[B|4KWH|T3]

Originariamente inviato da DanieleC88

Trattandosi di PyCon penso che fosse proprio una lista (non esiste un tipo "array" vero e proprio in Python).

Mi sembrerebbe strano o l'avrebbero chiamata lista. Boh

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.