[Resolvido] Merg Sort

[kilha 0]

Bom é o seguinte to tentando implementar o merge sort no visualg mas consegui dar o primeiro passo faz 3 dias que estou pesquisando mas não acho em lugar algum em portugol so em linguagens especificas, estou no primeiro periodo de sistemas de informação não tenho conhecimento em linguagem a não ser o portugol, entendi a logica do algoritmo, mas não consigo fazer isto no papel ate o presente momento saiu isto aqui :

 

procedimento mergesort(i,f:inteiro)
var
m: inteiro
inicio
se (i < f) entao
m <- (i + f)/2
mergesort(i, m)
mergesort(m+1, f)
intercala(i, m, f)
fim
fimse
fimprocedimento

não estou conseguindo fazer a segunda parte do algoritmo que é a intercalação so achei em C, mas não consigo traduzir para portugol. segue:

 

void merge(int vec[], int vecSize) {
  int mid;
  int i, j, k;
  int* tmp;
 
  tmp = (int*) malloc(vecSize * sizeof(int));
  if (tmp == NULL) {
	exit(1);
  }
 
  mid = vecSize / 2;
 
  i = 0;
  j = mid;
  k = 0;
  while (i < mid && j < vecSize) {
	if (vec[i] < vec[j]) {
	  tmp[k] = vec[i];
	  ++i;
	}
	else {
	  tmp[k] = vec[j];
	  ++j;
	}
	++k;
  }
 
  if (i == mid) {
	while (j < vecSize) {
	  tmp[k] = vec[j];
	  ++j;
	  ++k;
	}
  }
  else {
	while (i < mid) {
	  tmp[k] = vec[i];
	  ++i;
	  ++k;
	}
  }
 
  for (i = 0; i < vecSize; ++i) {
	vec[i] = tmp[i];
  }
 
  free(tmp);

 

Espero que me ajudem com este problema !!!!!!!! http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

[quitZAUMMM 18]

como você tentou, deixa eu ver!

 

[]s

[kilha 0]

como você tentou, deixa eu ver!

 

[]s

+ou- assim :

 

procedimento intercala (v[x],tam:inteiro)

 

Var

 

mid,i,j,k: inteiro

int* tmp // não sei que atribui o *

 

tmp <- (int*) malloc(tam * sizeof(int)); // nao entendi

 

se (tmp <> NULL) então // nao achei o fimse

 

mid <- tam / 2; (tam = tamanho do vetor)

 

i <- 0;

j <- mid;

k <- 0;

 

enquanto (i < mid && j < tam) faca // &&=?

se (v < v[j]) entao

tmp[k] = v;

i<- i+1;

senao

tmp[k] <- v[j];

j<-j+1;

k<-k+1;

 

se (i <> mid) entao \\ entendi que == é <>(diferente)

enquanto (j < tam)

tmp[k] <-v[j];

j<-j+1;

k<-k+1;

senao

enquanto (i < mid) faca

tmp[k] <- v;

i<-i+1;

k<-k+1;

 

para (i de 0; i < vecSize; ++i) // (para i de 1 ate tam passo +1) não sei se é isso

v = tmp;

 

free(tmp); // não entendi.

 

 

Não localizei os FIMSE, imagino que seja por ae ...

qq c acha ? http://forum.imasters.com.br/public/style_emoticons/default/upset.gif

[quitZAUMMM 18]

Olha n cheguei a rodar, tenho ctz q jah fiz isso em portugol + o site da minha facu dos anos anteriores num ta abrindo..

entaum.. achei esse código na net, vo tentar passar pra portugol, vamos ver:

Procedimento intercala(inteiro M[50], inteiro p, inteiro q, inteiro r)
	inteiro prim, res, seg, k;
	inteiro C[50];
	prim <- res <- p;
	seg <- q+1;
	Enquanto (prim<=q e seg<=r){
		Se(M[prim]<=M[seg]) então
			C[res] <- M[prim];
			prim<-prim+1;
		senao
			C[res] <- M[seg];
			seg<-seg+1;
		fim_se
		res<-res+1;
	Fim_Enquanto
	Se(prim>q) então
		Para k de seg até k<=r faça
			C[res] <- M[k];
			res<-res+1;
		Fim_Para
	Senão
		Para k de prim até k<=q faça
			C[res] <- M[k];
			res<-res+1;
		Fim_Para
	Fim_Se
	Para k de p até k<=r faça
		M[k] = C[k];
	Fim_Para
Fim_Procedimento

[]s

[kilha 0]

Consegui termina, dei mais umas pesquisadas, contudo quero agradeçer ao quitZAUMMM pelos Help´s, abaixo segue a implementação rodando direitinho no Visualg, não está muito bonito estéticamente fiz so para testar, como não achei desta forma , venho disponibilizar para quem quiser..

 

[]´s

 

 

algoritmo "MergeSort"

// Autor : Rafael  Rocha
// Data : 29/06/2009
// Seção de Declarações
var

Procedimento MERGESORT(inici, fim: inteiro )
var
meio:inteiro
inicio
se (inici <  fim) entao
meio<-(inici + fim) DIV 2
MERGESORT (inici, meio)
MERGESORT (meio+1, fim)
MERGE (inici, meio, fim)
fimse
fimprocedimento


procedimento MERGE (inici, meio, fim: inteiro )
var
h,i,j,k:inteiro
b: vetor [1..10] de inteiro
inicio

h<-inici;
i<-inici;
j<-meio + 1;
enquanto (h<=meio) e (j<=fim) faca

se A[h] <= A[j] entao
	 B[i]<-A[h];
	 h<- h + 1;
senao
   B[i]<-A[j];
	j<- j + 1;
fimse
i<- i + 1;
fimenquanto
se h > meio entao
Para k de j ate fim faca
B[i]<- A[k];
i<- i + 1;
fimpara
senao
Para k de h ate meio faca
B[i]<-A[k];
i<- i + 1;
fimpara
fimse
para k de inici ate fim faca
A[k]<-B[k];
fimpara
fimprocedimento
a: vetor [1..10] de inteiro
x,inici,fim:inteiro

inicio
// Seção de Comandos 

aleatorio 0,30

para x de 1 ate 10 faca
	 leia (a[x])
fimpara

inici<-1
fim<-10
MERGESORT(inici, fim )

para x de 1 ate 10 faca
	 escreva (a[x])
fimpara
fimalgoritmo

[quitZAUMMM 18]

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

Obrigado por compartilhar a solução!

 

[]s

[JuCaJoSi 0]

Ajudou muito kilha.

vlw mesmo!!!

E difícil achar na web codigos de visualg e pascal.

 

:clap: