MERGE SORT

di il
3 risposte

MERGE SORT

Stavo vedendo qualche lezione sul merge sort, e selezionando questo:

https://www.youtube.com/watch?v=GCae1WNvnZ

ad un certo punto visualizza questo codice, è una chiamata ricorsiva alla funzione o sbaglio?

for(i=1;i<n;i=2i)
     {
           for(j=0;j<n;j=j+2i)
           {
                  MERGE_R(&A[j]. i,min(2i, size – j);
            }
     }

3 Risposte

  • Re: MERGE SORT

    Giacomo_made4core ha scritto:


    Stavo vedendo qualche lezione sul merge sort, e selezionando questo:

    https://www.youtube.com/watch?v=GCae1WNvnZ

    ad un certo punto visualizza questo codice, è una chiamata ricorsiva alla funzione o sbaglio?
    
    for(i=1;i<n;i=2i)
         {
               for(j=0;j<n;j=j+2i)
               {
                      MERGE_R(&A[j]. i,min(2i, size – j);
                }
         }
    
    Il codice di questo merge sort è diverso dal classico, sono fuori casa e non ho tempo per guardarlo, ad ogni modo il classico merge sort richiama se stesso ricorsivamente a destra e a sinistra di un punto centrale, per poi effettuare una chiamata ricorsiva di una terza funzione, solitamente chiamata Merge() che prende in input due array ordinati e ne restituisce uno solo completamente ordinato. Ovviamente con un approccio bottom-up, parte dagli ultimi risultati ottenuti (cioè un array di un solo elemento quindi ordinato) e risale nelle varie chiamate ricorsive ottenendo così un array ordinato.
    Ti consiglio di leggere qualcosa sulla tecnica di programmazione "Divide et Impera" prima di addentrarti nel merge sort e soprattutto di leggere qualcosa di scritto prima di provare con i video, che possono essere utili solo per visualizzare meglio ciò che succede ad ogni chiamata

    Inviato dal mio A0001 utilizzando Tapatalk
  • Re: MERGE SORT

    Quindi in pratica è una chiamata ad un altra funzione?
  • Re: MERGE SORT

    Giacomo_made4core ha scritto:


    quindi in pratica è una chiamata ad un altra funzione?
    Se si tratta di Merge() si, è una chiamata ad un'altra funzione chr viene effettuata ad ogni chiamata destra e sinistra di Merge-Sort

    Inviato dal mio A0001 utilizzando Tapatalk
Devi accedere o registrarti per scrivere nel forum
3 risposte