.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- esercizio 2 scritto algoritmi (http://www.dsy.it/forum/showthread.php?threadid=44106)

esercizio 2 scritto algoritmi

Ciao a tutti,
stavo guardando la soluzione proposta dal professore dell'esrcizio 2:

*********************
2. Considerate la seguente sequenza di numeri memorizzata in un array che deve essere ordinata in modo crescente:
423 451 516 491 333 243 216 126 321
**************************************

a me come soluzine viene:
321 126 216 243 333 423 491 516 451

invece il prof scrive:
243 321 126 216 333 423 491 516 451


Qualcuno ha fatto questo esercizio?
può postare i passaggi?

Grazie

praticamente devi scorrere l'array in parallelo da sinistra verso destra cercando il primo elemento maggiore del perno, e da destra verso sinistra cercando il primo
elemento minore del perno. trovati questi due elementi li scambio.
Quando l'elemento maggiore si trova alla destra di quello minore(oppure quando l'elemento minore si trova alla sinistra di quello maggiore,è la stessa cosa),scambio il perno con l'elemento minore.
Quindi :
423 451 516 491 333 243 216 126 321
il perno è 423
scorro da destra verso sinistra cercando il primo elemento maggiore di 423,trovo 451.
scorro da sinistra verso destra cercando il primo elemento minore di 423,trovo 321.
scambio gli 451 e 321.
423 321 516 491 333 243 216 126 451
423 321 126 491 333 243 216 516 451
423 321 126 216 333 243 491 516 451
ora scambio il perno con il 243
243 321 126 216 333 423 491 516 451

Re: esercizio 2 scritto algoritmi

Originally posted by lem_123
Ciao a tutti,
stavo guardando la soluzione proposta dal professore dell'esrcizio 2:

*********************
2. Considerate la seguente sequenza di numeri memorizzata in un array che deve essere ordinata in modo crescente:
423 451 516 491 333 243 216 126 321
**************************************

a me come soluzine viene:
321 126 216 243 333 423 491 516 451

invece il prof scrive:
243 321 126 216 333 423 491 516 451


Qualcuno ha fatto questo esercizio?
può postare i passaggi?

Grazie

Re: Re: esercizio 2 scritto algoritmi

Originally posted by Cronovirus
Ma sai scherzando.. Vero?

grazie

Originally posted by m.m
praticamente devi scorrere l'array in parallelo da sinistra verso destra cercando il primo elemento maggiore del perno, e da destra verso sinistra cercando il primo
elemento minore del perno. trovati questi due elementi li scambio.
Quando l'elemento maggiore si trova alla destra di quello minore(oppure quando l'elemento minore si trova alla sinistra di quello maggiore,è la stessa cosa),scambio il perno con l'elemento minore.
Quindi :
423 451 516 491 333 243 216 126 321
il perno è 423
scorro da destra verso sinistra cercando il primo elemento maggiore di 423,trovo 451.
scorro da sinistra verso destra cercando il primo elemento minore di 423,trovo 321.
scambio gli 451 e 321.
423 321 516 491 333 243 216 126 451
423 321 126 491 333 243 216 516 451
423 321 126 216 333 243 491 516 451
ora scambio il perno con il 243
243 321 126 216 333 423 491 516 451

Sempre in merito all'esercizio 2 ma riguardo il punto b, la sequenza risultante anziché 516 491 423 451 333 243 216 126 321, non dovrebbe essere
516 491 423 451 333 321 243 216 126?

Re: Re: Re: esercizio 2 scritto algoritmi

Originally posted by lem_123
azz... perdonami se ho offeso la tua intelligenza..

Originally posted by Cic
Sempre in merito all'esercizio 2 ma riguardo il punto b, la sequenza risultante anziché 516 491 423 451 333 243 216 126 321, non dovrebbe essere
516 491 423 451 333 321 243 216 126?

Originally posted by m.m
praticamente devi scorrere l'array in parallelo da sinistra verso destra cercando il primo elemento maggiore del perno, e da destra verso sinistra cercando il primo
elemento minore del perno. trovati questi due elementi li scambio.
Quando l'elemento maggiore si trova alla destra di quello minore(oppure quando l'elemento minore si trova alla sinistra di quello maggiore,è la stessa cosa),scambio il perno con l'elemento minore.
Quindi :
423 451 516 491 333 243 216 126 321
il perno è 423
scorro da destra verso sinistra cercando il primo elemento maggiore di 423,trovo 451.
scorro da sinistra verso destra cercando il primo elemento minore di 423,trovo 321.
scambio gli 451 e 321.
423 321 516 491 333 243 216 126 451
423 321 126 491 333 243 216 516 451
423 321 126 216 333 243 491 516 451
ora scambio il perno con il 243
243 321 126 216 333 423 491 516 451

Originally posted by alexx
ciao! posso chiedervi una cosa? il perno viene scambiato con il numero corrispondente all'indice in cui sono arrivato dopo che ho finito di scorrere l'array? ovvero dove si incontrano i due indici?
e dopo comunque il perno rimane quello iniziale?

facendo lo stesso ragionamento sul esercizio quick sort del secondo esame risulterebbe:
sequenza=>8 4 15 12 10 7 11 9 13 perno=8

1)4 7 12 10 15 11 9 13
scorrendo arrivo fino a che i=j cioè sull'elemento 7 e scambio il perno
2)7 4 8 12 10 15 11 9 13

E' corretto il ragionamento?

grazie per l'aiuto

boh mi sa che non c'è nessuno che risponde. mi sa che alcune cose mi tocca chiederle al prof