Newsgroup: it.scienza.informatica
Titolo: Lo StupidSort

Salve Ng :)
lo StupidSort è, ovviamente, un nome di fantasia di un algoritmo che serve 
per esercitarsi. Tra i punti da svolgere vi è la complessità temporale
nel caso peggiore... e non so calcolarla! O_o
Mi sono fatto qualche esempio pratico per provare ad avere un' intuizione, e 
scritto uno pseudocodice "al volo", ma non mi si è aperta molto la mente :-/
Potreste darmi una mano? Ecco come opera lo stupidsort:
---------
L'algoritmo stupidSort opera nel modo seguente. Partendo dall'inizio dell'array, 
esegue una scansione finchè non trova due elementi consecutivi nell'ordine 
sbagliato: in tal caso, scambia gli elementi ed inizia una nuova scansione, 
sempre partendo dalla prima posizione dell'array.
- Dimostrare il tempo di esecuzione dell'algoritmo stupidSort nel caso 
migliore e nel caso peggiore.
-Mostrare una implementazione iterativa ed una implementazione ricorsiva 
dell'algoritmo stupidSort.
-Discutere l'uso di memoria nelle due implementazioni.
----------------
Mi sembra ovvio che il caso migliore risulta quando l'array è già ordinato, 
dunque con una passata l'algoritmo se la cava (dunque posso affermare O(n)).
Il caso peggiore dovrebbe vedere un array ordinato in modo decrescente (se 
stiamo ordinando dal più piccolo al più grande,viceversa altrimenti).
Ho scritto anche una pseudo-implementazione di questo stupidSort:
http://slide.altervista.org/stupidSort.txt
Fatemi capire come si ragione perchè con la stima delle complessità son 
messo proprio male :_(
Grazie per la pazienza e buon proseguimento,
Shad 


Lo StupidSort in realta' e' il BubbleSort il caso peggiore e' quando
gli elementi sono ordinati nel verso opposto (ad esempio se devo
ordinare in modo crescente il caso peggiore sarà l'ordinamento
decrescente) in tal caso ci vorranno (N*(N-1))/2  sostituzioni di
conseguenta ha una complessita' nel caso pessimo quadratica.
Paggio

 conseguenta ha una complessita' nel caso pessimo quadratica.
A me non sembra proprio il bubble sort, in quanto agisce più "stupidamente".
Con il bubble sort abbiamo la certezza che l'elemento maggiore sia portato 
in fondo alla sequenza ad ogni "passata";
mentre questo stupid sort *appena* effettua uno scambio rinizia da capo.
Ricordo che ero stato un altro po' a ragionare su quest'esercizio e mi ero 
convinto di un O(n^3), ma ho scordato come ci ero arrivato :-/
Grazie per la risposta,
S.

Si hai ragione non avevo letto che riniziava da capo.



Divide ed impera.
Se il problema ti sembra troppo complicato scomponilo, risolvi
le parti e poi riassemblale una ad una.
Lo StupidSort ad ogni iterazione sposta una sola coppia
di una posizione (scambiando i due elementi).
Il caso peggiore per la singola iterazione e' (N-1) confronti
(quando si fa un solo scambio in fondo all'array, oppure quando
  non si fa alcun scambio ma si devono scansionare tutti gli elementi
  per capirlo).
Nel caso migliore (array gia ordinato) basta una sola iterazione
e per essa si realizza il caso peggiore dell'iterazione(non
dell'ordinamento di tutto l'array, visto che
per accorgersi che non c'e' stato alcun scambio e fermarsi
bisogna scorrere tutti gli elementi)
ed in tal caso la complessita' e' O(n).
Per il caso peggiore dell'ordinamento di tutto l'array
serve un ulteriore scomposizione del problema: bisogna valutare
quante iterazioni "stupide" servono per mettere nella posizione
finale almeno un elemento.
Se un elemento ha come posizione "in ordine" l'indice k
ed invece sta nella posizione j, servono almeno abs(k-j) iterazioni
per "metterlo in posizione".
Nel caso peggiore in cui l'array e' ordinato alla rovescia
servono N-1 iterazioni per portare in posizione il primo elemento
N-2 iterazioni per portare in posizione il secondo elemento ecc. ecc.
quindi nel caso peggiore si hanno [(n-1)+(n-2)+...+3+2+1] iterazioni
ovvero [ (n-1)*n/2 ] (formula di gauss)
ovvero O(n^2) ITERAZIONI (ora manca solo il costo computazionale
delle singole iterazioni).
Abbiamo gia visto che il caso "peggiore" di una singola iterazione
e' O(n), nel caso peggiore dell'array le iterazioni hanno
complessita media O(n/2) che equivale ad O(n)
quindi mettendo tutto insieme otteniamo
O(n* (n^2)) = O(n^3)
L. Micheletto
N.B. riguardo la formula di Gauss, visto che in casi simili
      si usa spesso, penso sia il caso di ricordare
      da cosa ha origine, perche sapendolo e' piu facile
      da ricordare:
      se consideri le unita degli interi
      come dei "quadratini" la somma [(n-1)+(n-2)+...+3+2+1]
      corrisponde ad un "triangolo rettangolo" di quadratini
      con i cateti che misurano n-1 quadratini
      la cui area corrisponde alla somma e che coincide
      con ((n-1)*n)/2 (e' simile all'area del triangolo
      ma "discretizzata in quadratini")
Es: N = 5
     (N-1)+..+2+1 = 4+3+2+1 = (4*5)/2
Ovvero in "quadratini" e' l'area di un triangolo rettangolo
i cui cateti sono ampi (N-1)= 4 quadratini
*
**
***
****

      da cosa ha origine,
[CUT]
Per ricordarla mi sono memorizzato l'evento storico: la maestra che, per 
punizione, dice a Gauss (di otto anni)
di sommare i primi 100 numeri :)
Saluti a tutti,
Shad