casacup
08-03-2007, 01:05
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 :D
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 :D