preparando fond inf 2... problema merge sort...

[casacup]

salve a tutti!
mi sto dando alla pazza gioia con quelle 6-7-8 ore al giorno di informatica 2 causa esami... e sono arrivato al fatidico merge sort. Il linguaggio è il c++, l'algoritmo è il merge sort creato per evitare troppa occupazione in memoria centrale (comunque buono per dim input < 10^6).

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<conio.h>
using namespace std;


const int n_max=1000;
typedef int tipo_elementi;
struct  tipo_insieme{
                     tipo_elementi elementi[n_max];
                     int lunghezza;
                     };
tipo_insieme I,I1,I2;

void creainsieme(tipo_insieme &Insieme)
{
     cout<<"inserisci il numero di elementi dell'insieme ";
     cin>>Insieme.lunghezza;
     for(int i=0;i<Insieme.lunghezza;i++)
     { 
              cout<<"inserisci l'elemento  "<<i<<"  ";
              cin>>Insieme.elementi[i];
     }
}                       



void merge(tipo_insieme insieme1,tipo_insieme insieme2,tipo_insieme &insieme)
{ 
     int k=0,j=0,i=0;
                            while((i<insieme1.lunghezza)&&(j<insieme2.lunghezza))
                            {
                            if(insieme1.elementi[i]<insieme2.elementi[j])
                            {insieme.elementi[k]=insieme1.elementi[i];
                            i++;}
                            else
                            {
                            insieme.elementi[k]=insieme2.elementi[j];
                            j++;
                            }
                            k++;
                            }        
                            
                            
                            while(i<insieme1.lunghezza) 
                                {     insieme.elementi[k]=insieme1.elementi[i];
                                i++;k++;}
                                    
                            while(j<insieme2.lunghezza) 
                                {     insieme.elementi[k]=insieme2.elementi[j];
                                j++;k++;}
                           insieme.lunghezza=k;   
                                 
}



void mergesort(tipo_insieme &seq)
{
     tipo_insieme seq1,seq2;
     
     if (seq.lunghezza!=1)     {
                               seq1.lunghezza=(seq.lunghezza/2);
                               if(seq.lunghezza==(seq1.lunghezza*2))
                               seq2.lunghezza=(seq.lunghezza/2);
                               else
                               seq2.lunghezza=(seq.lunghezza/2)+1;                               
                               for(int i=0;i<seq1.lunghezza;i++)
                               seq1.elementi[i]=seq.elementi[i];
                               
                               //cout<<seq1.lunghezza<<"    j    "<<seq2.lunghezza<<"     ";       stampa di controllo
                               for(int i=0;i<seq2.lunghezza;i++)
                               seq2.elementi[i]=seq.elementi[i+seq1.lunghezza];
                               
     mergesort(seq1);
     mergesort(seq2);
     merge(seq1,seq2,seq);
     }
   
}      





void stampainsieme(tipo_insieme Insieme1)
{
     for (int i=0;i<Insieme1.lunghezza;i++)
       cout<<"   "<<Insieme1.elementi[i];
       cout<<endl;
}




int main()
{
creainsieme(I1);
mergesort(I1);
stampainsieme(I1);
system("pause");
return 0;
}

ora, da quello che ho capito io in pratica il sistema merge-sort prende un array di dimensione n ed, in maniera ricorsiva, lo divide in due (quindi i due array vengono divisi in due, che vengono ridivisi in due e così via) fino ad avere n variabili allocate corrispondenti agli n elementi dell'array.
dopo di ciò prende e comincia a fondere: risalendo "sull'albero" appena creato prende prima due elementi adiacenti, li ordine e li fonde, e così poi fa con tutti gli altri, e la stessa cosa fa con tutti gli array appena creati, e così via fino ad avere due unici array di dimensione n/2, già ordinati al loro interno, che vengono fusi ed ordinati...

il ragionamento - spero - sia questo.

c'è solo un problema: NON SO COSA SUCCEDE A LIVELLO DI CODICE.....

nel senso, non è che non riesco ad interpretare quanto scritto sopra, ma non ne riesco ad avere la visione d'insieme... e avrei bisogno che quale pia pia ma tanto pia persona mi dica, su un esempio, chessò, di un array di dimensione 5 o 6 cosa succeda passo passo ad ogni attivazione (naturalmente parlo del merge sort... la funzione leggi e stampa le so interpretare...).

mi sapreste aiutare? please...

grazie al santo/santi che mi daranno una mano

[luxorl]

Qui trovi spiegazioni e esempio

http://it.wikipedia.org/wiki/Merge_sort

[casacup]

già visto... purtroppo l'articolo su wikipedia non risponde alla mia domanda, ovvero non spiega per bene cosa accade ad ogni attivazione...

[tomminno]

Ma un compilatore per eseguire il debug passo passo no?

[casacup]

no...devo proprio capirlo per bene a livello teorico, per essere in grado poi di utilizzarlo per bene...

[tomminno]

Originariamente inviato da casacup

no...devo proprio capirlo per bene a livello teorico, per essere in grado poi di utilizzarlo per bene...

Per capirlo a livello teorico ti basta studiare il merge sort su un qualunque manuale, se vuoi capire il funzionamento passo passo del codice (come chiedevi) ti serve un compilatore, una spiegazione a parole non farebbe altro che ricalcare il funzionamento dell'algoritmo scritto su qualunque manuale.

[casacup]

purtroppo sto studiando sul libro scritto dal prof... nel quale il merge è spiegato abbastanza bene, il merge sort invece non ha neanche una riga di spiegazione (riferendomi a quello riportato basato sugli indici)... ecco, in particolare è sugli indici che mi impiccio...