Come funziona l'ordinamento ingenuo?

di il
6 risposte

Come funziona l'ordinamento ingenuo?

Tra qualche giorno ho un compito sui metodi di ordinamento e siccome è il primo anno che faccio programmazione non ci ho capito niente

6 Risposte

  • Re: Come funziona l'ordinamento ingenuo?

    Ma quali metodi di ordinamento ti interessano?...ce ne sono un infinità...io conosco bene due dei più importanti che sono il bubble sort ed il selection sort...
  • Re: Come funziona l'ordinamento ingenuo?

    Quello che tu chiami ordinamento ingenuo, è più o meno quello che comunemente si usa tenendo in mano un mazzo di carte. L'idea è di cercare l'elemento più piccolo, tra quelli che ti rimangono da ordinare, e metterlo all'inizio (tendenzialmente lo si scambia di posto con il primo) di tale "sotto-vettore".
    All'inizio hai tutto il vettore da ordinare, quindi cerchi il più piccolo e lo metti nella prima posizione.
    Al secondo giro cerchi il più piccolo, partendo dal secondo, e lo metti nella seconda posizione.
    Poi cerchi il più piccolo partendo dal terzo
    poi dal quarto, poi dal quinto, ecc...

    esempio:

    10, 20 , 15, 7, 12, 18, 25, 2, 22, 19.
    Primo giro: il più piccolo è il 2, e lo scambio con il 10 al primo posto. Ottengo:
    2, 20, 15, 7, 12, 18, 25, 10, 22, 19.
    Secondo giro: il più piccolo, partendo dal secondo è il 7, e lo metto al posto del 20 in posizione 2. Ottengo:
    2, 7, 15, 20, 12, 18, 25, 10, 22, 19.
    Terzo giro: partendo dal terzo elemento, il più piccolo è il 12, quindi lo scambio con il 15 in posizione 3:
    2, 7, 12, 20, 15, 18, 25, 10, 22, 19.
    Giro 4: il più piccolo del sottovettore è il 15, e lo scambio con il 20 in posizione 4:
    2, 7, 12, 15, 20, 18, 25, 10, 22, 19.
    Giro 5: ...

    Prova a finire tu...
  • Re: Come funziona l'ordinamento ingenuo?

    Partendo da quinto elemento il più piccolo è 18..quindi lo scambio con il 20..?
  • Re: Come funziona l'ordinamento ingenuo?

    Mr.Crow ha scritto:


    ma quali metodi di ordinamento ti interessano?...ce ne sono un infinità...io conosco bene due dei più importanti che sono il bubble sort ed il selection sort...
    il mio prof insiste molto su bubble sort..io lo so a memoria..però non me ne faccio niente se non capisco come funziona e in quali occasioni va uitlizzato e come va utilizzato..
  • Re: Come funziona l'ordinamento ingenuo?

    Arkan ha scritto:


    partendo da quinto elemento il più piccolo è 18..quindi lo scambio con il 20..?
    Esatto. E si ottiene:
    2, 7, 12, 15, 18, 20, 25, 10, 22, 19.
  • Re: Come funziona l'ordinamento ingenuo?

    Arkan ha scritto:


    il mio prof insiste molto su bubble sort..io lo so a memoria..però non me ne faccio niente se non capisco come funziona e in quali occasioni va uitlizzato e come va utilizzato..
    Il bubble sort mi sembra spiegato abbastanza chiaramente su wikipedia. Io lo trovo tanmente semplice in sè, che non riesco a trovare un modo più semplice per spiegarlo.
    A meno che il problema non stia in come implementarlo, ma nel dimostrare che è corretto.

    Esso consiste nello scorrere tutto il vettore più volte, confrontando ogni elemento con il successivo, e scambiandoli di posto se il secondo è più grande del primo. L'ultima scansione della sequenza è quella in cui non si fa nessuno spostamento. Per riprendere l'esempio di prima, partendo da:

    10, 20 , 15, 7, 12, 18, 25, 2, 22, 19

    1 e 2 due sono in ordine (10,20),

    2 e 3 vanno scmabiati (20,15)
    10, 15, 20, 7, 12, 18, 25, 2, 22, 19

    3 e 4 (del nuovo vettore) vanno scambiati (20,7) -> (7,20)
    10, 15, 7, 20, 12, 18, 25, 2, 22, 19

    4 e 5 vanno scambiati (20,12) -> (12,20)
    10, 15, 7, 12, 20, 18, 25, 2, 22, 19

    5 e 6 vanno scambiati (20,18) -> (18,20)
    10, 15, 7, 12, 18, 20, 25, 2, 22, 19

    6 e 7 sono in ordine (20,25)

    7 e 8 vanno scambiati (25,2) -> (2,25)
    10, 15, 7, 12, 18, 20, 2, 25, 22, 19

    8 e 9 vanno scambiati (25,22) -> (22,25)
    10, 15, 7, 12, 18, 20, 2, 22, 25, 19

    9 e 10 vanno scambiati (25,19) -> (19,25)
    10, 15, 7, 12, 18, 20, 2, 22, 19, 25

    A questo punto si riparte dall'inizio del vettore.
    1 e 2 sono a posto (10,15)

    2 e 3 vanno scambiati (15,7 -> (7,15)
    10, 7, 15, 12, 18, 20, 2, 22, 19, 25

    3 e 4 ....

    Michele
Devi accedere o registrarti per scrivere nel forum
6 risposte