C Ordenação de Strings com merge sort

[Danielle Emely]

Olá, estou realizando um trabalho em que preciso ordenar um vetor de strings com merge sort, no entanto, estou com dificuldade em como vou fazer as comparações entre nomes de pessoas, pensando nas possibilidades de nomes com letra inicial igual, aí sendo preciso olhar as demais letras pra ver qual nome virá primeiro, e de nomes iguais precisando olhar os sobrenomes pra ver qual dos nomes virá primeiro. Alguém pode me orientar em como vou fazer essa ordenação usando merge sort?  

[Danielle Emely]

 

[devair1010]

@Danielle Emely    você quer usar o mergesort  ?   ou pode ser outro método de ordenação  , tipo o mais fácil que é o bubblesort ?    o strcmp compara os nomes pela primeira letra , então creio que para isso você precisa fazer manualmente comparado cada caractere .

[Danielle Emely]

[

 

[arfneto]

Em 02/10/2019 às 01:05, Danielle Emely disse:

trabalho em que preciso ordenar um vetor de strings com merge sort, no entanto, estou com dificuldade em como vou fazer as comparações entre nomes de pessoas, pensando nas possibilidades de nomes com letra inicial igual, aí sendo preciso olhar as demais letras pra ver qual nome virá primeiro, e de nomes iguais precisando olhar os sobrenomes pra ver qual dos nomes virá primeiro

 

Olá Danielle

 

Até aqui seu problema não tem a ver com o método de sort. Trata-se apenas da rotina de comparação. Escreva apenas a rotina de comparação e teste em separado. Não faz diferença para o método de sort que vai usar.

 

Vai escrever isso em C ou C++ ou C#?

 

Exemplo de caso em C

Apenas para ajudar a entender: C tem acho que em stdlib.h

void qsort (   void*     vetor, 
               size_t    quantos, 
               size_t    tamanho, 
               int (*compara)(const void*  valor1, const void* valor2)
           );

e usa o método quicksort que é bem parecido com o merge sort. A chave para esse método é a compara(), que retorna -1, 0 ou 1 conforme a posição relativa dos dois parâmetros valor1 e valor2.

E para mudar a ordem de classificação você só precisa mudar a função....

 

Exemplo de caso em C++

Na biblioteca padrão do C++ acho que em <algorithm> tem a função sort

    void sort(  Iterator primeiro, 
                Iterator ultimo, 
                Bool     compara
              );

e nesse caso primeiro e ultimo são iteradores apontando para o primeiro valor e o indicador de último valor da série, e compara  é uma função que retorna true se os dois valores já estão na ordem, false se devem ser invertidos

 

exemplo de caso em C#

ih... Não programo em C#

 

Em resumo

escreva uma função compara() que compara os dois nomes, e teste com a linguagem que precisar usar. E depois escreva o seu sort(). Merge Sort no caso. Merge sort, selection sort, bubble sort, quicksort, XYZSort não faz diferença: já terá sua função compara() pronta e testada... E sem ela não vai classificar nada.

 

C strcmp()

int strcmp(const char *str1, const char *str2)

retorna <0, 0 ou > 0 conforme o valor de str1 e str2 e serve direitinho para o que precisa. Pode usar essas funções ou tem que escrever sua comparação?

 

Postei dias atrás aqui um programa em C que usava qsort() eu acho, em C. e tinha umas funções de comparação, claro.

Avise se precisar e eu procuro aqui. Ou use as ferramentas do forum.

 

Escreva mais

 

[Danielle Emely]

@arfneto  e @@devair1010 Eu consegui implementar com merge sort e bubble sort!! Tentei com o bubble e vi o que errei no merge, como vou precisar de uma struct, fiz uma de teste. Querem ver o código? Tava pensando em postar amanhã mais tarde, mas não sei se faço outro fórum pra isso

adicionado 5 minutos depois

@arfneto  é em c 

[arfneto]

1 hora atrás, Danielle Emely disse:

@arfneto  e @@devair1010 Eu consegui implementar com merge sort e bubble sort!! Tentei com o bubble e vi o que errei no merge, como vou precisar de uma struct, fiz uma de teste. Querem ver o código? Tava pensando em postar amanhã mais tarde, mas não sei se faço outro fórum pra isso

adicionado 5 minutos depois

@arfneto  é em c 

 

muito bom!  Parabéns

 

Então já deve ter entendido porque 100% dos métodos admite --- ou exige --- um ponteiro para uma rotina de comparação. Para uma struct particular não tem como o método saber como classificar. Pode ser que o critério de classificação também seja parâmetro por exemplo. Considere

• :Uma série de struct de cadastro pode ser classificada ora por nome, ora por CPF ora por CEP do endereço de entrega por exemplo
• Uma série de struct de pedidos para envio pode ser classificada através de uma consulta ao sistema de frete no momento da classificação, mas só se o sistema estiver on-line......
• Você pode estar testando suas rotinas de sort então claro quer testar com os mesmos critérios de classificação

Imagino que se referia a postar seu código em outro tópico. Meu palpite seria para postar aqui mesmo. E abrir outro tópico apenas se tiver outra dúvida ou comentar algo diferente sobre suas versões de sort(). Comparou os tempos de execução? 

[Danielle Emely]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef struct{
	int* vet;
	char** vetNome;
}Teste;
void mergeSort(Teste, int, int );
void intercala(Teste, int, int , int);
void bubbleSort(Teste test, int tamanho);
int pesquisaBin(Teste, char* chave, int, int);
int main(){
	Teste test;
	test.vetNome = malloc(sizeof(char*) * 7);
	for (int i = 0; i < 100; i++){
		test.vetNome[i] = malloc(sizeof(char) *100);
	}
	strcpy(test.vetNome[0],"Aberlado Barbosa\n");
	strcpy(test.vetNome[1], "José Frances\n");
	strcpy(test.vetNome[2], "Barbara Vitoria\n");
	strcpy(test.vetNome[3], "Maria Silva\n");
	strcpy(test.vetNome[4], "Bia Menezes\n");
	strcpy(test.vetNome[5], "Samile Tania\n");
	strcpy(test.vetNome[6], "Maria Souza\n");
	test.vet = malloc(sizeof(int) * 5);
	int k = 0;
	for (int i = 4; i >= 0; i--){
		test.vet[k] = i;
		k++;
	}
	mergeSort(test,0,6);
	//bubbleSort(test,5);
	int pos = pesquisaBin(test, "José Frances\n", 0, 6);
	for (int i = 0; i < 7; i++){
		printf("posição %d, nome: %s\n",i,test.vetNome[i] );
	}
	printf(" Posicao de José: %d\n", pos);
	return 0;
}
// ordenação com merge sort
void mergeSort(Teste test, int inicio, int fim){
	if(inicio < fim){
		int meio = ((inicio + fim)/2);
		mergeSort(test, inicio, meio);
		mergeSort(test, meio + 1, fim);
		intercala(test, inicio, meio, fim);
	}
}
void intercala(Teste test, int inicio, int meio, int fim){
	int tamanho;
	int i, j, k, esq, dir;
	int fimEsq = 0, fimDir = 0;
	tamanho = fim -inicio + 1;
	esq = inicio;
	dir = meio + 1;
	char** vetOrdenado;
	vetOrdenado = malloc(sizeof(char*) * tamanho);
	for (int l = 0; l < tamanho; l++){
		vetOrdenado[l] = malloc(sizeof(char) *100);
	}
	if(vetOrdenado != NULL){
		for(i = 0; i < tamanho; i++){
			int tam1 = strlen(test.vetNome[esq]);
			int tam2 = strlen(test.vetNome[dir]);
			int tamMax;
			if(tam1>tam2){
				tamMax = tam1;
			}else{
				tamMax = tam2;
			}
			if(!fimEsq && !fimDir){
				if(strncmp(test.vetNome[esq], test.vetNome[dir], tamMax) < 0)
					strcpy(vetOrdenado[i], test.vetNome[esq++]);
				else
					strcpy(vetOrdenado[i], test.vetNome[dir++]);
			
				if(esq > meio)
					fimEsq = 1;
				if(dir > fim)
					fimDir = 1;
			}else{
				if(!fimEsq)
					strcpy(vetOrdenado[i], test.vetNome[esq++]);
				else
					strcpy(vetOrdenado[i], test.vetNome[dir++]);
			}
		}
	}
	for(j=0,  k = inicio; j < tamanho;j++, k++){
		strcpy(test.vetNome[k], vetOrdenado[j]);
	}
}
//ordernação com bubble sort
void bubbleSort(Teste test, int tamanho){
	int i, continua, fim = tamanho;
	char* aux = malloc(sizeof(char)*50);
	do{
		continua = 0;
		for (i = 0; i < tamanho-1; i++){
			int tam1 = strlen(test.vetNome[i]);
			int tam2 = strlen(test.vetNome[i+1]);
			int tamMax;
			if(tam1>tam2){
				tamMax = tam1;
			}else{
				tamMax = tam2;
			}
			if(strncmp(test.vetNome[i], test.vetNome[i+1], tamMax) > 0){
				strcpy(aux,test.vetNome[i]);
				strcpy(test.vetNome[i],test.vetNome[i+1]);
				strcpy(test.vetNome[i+1],aux);
				continua=i;
			}
		}
		fim--;
	}while(continua!=0);
}
// pesquisa binária de strings
int pesquisaBin(Teste test, char* chave, int esq, int dir){
  int m;
  int tamanho = strlen(chave);
  if(strncmp(test.vetNome[esq], chave, tamanho) == 0){
    	return esq;
  }else if(strncmp(test.vetNome[dir], chave, tamanho) == 0){
  		return dir;
  		}else{
     		m = (esq + dir)/2;
    		if(strncmp(test.vetNome[m], chave, tamanho) < 0){
        	pesquisaBin(test, chave, m + 1, dir);
      		}else{
        	pesquisaBin(test, chave, esq, m - 1);
      }
  }
}

usei strncmp @arfneto assim como tinha dito para o@devair1010 , ele era bom ver casos de nomes iguais e sobrenomes diferentes. Ai tem as versões de ordenação bubble e merge, assim como busca binária. E o tempo de execução do merg é melhor no pior caso do que o pior caso do  bubble :). Muito obrigada, pessoal!! Espero ajudar quem precisa  

[arfneto]

Muito bem!

Boa ideia usar char** e alocar o vetor como fez. É exatamente assim que o compilador prepara o vetor de argumentos da linha de comando, argv, que é o char** mais declarado do universo  

 

Vejo que acabou não escrevendo a rotina única de comparação como te disse. Devia ter feito isso. O programa ficaria um pouco mais limpo e poderia como eu disse comparar mais facilmente os tempos de execução. Claro que tem o custo associado a chamar uma função.

 

Mais dois palpites

• Podia ter antes de tudo escrito uma função simples para mostrar o vetor na tela. Você sabe porque.
• Podia ter usado antes de tudo o qsort() da biblioteca padrão e a sua função compara() para validar as coisas sem testar duas coisas ao mesmo tempo.

O que eu falei sobre os tempos não era sobre a teoria dos algoritmos: eu falava sobre usar o próprio computador e seu programa para testar os tempos de classificação de cada método, usado algo como time() ou getTicks() ou sei lá.

 

De todo modo, parabéns. Legal você postar o código. É um problema clássico e pode ajudar muita gente.

[Danielle Emely]

@arfneto Ahh sim, agora ficou mais claro. Acho que interpretei mal :P, mas obrigada!!

[arfneto]

3 horas atrás, Danielle Emely disse:

@arfneto Ahh sim, agora ficou mais claro. Acho que interpretei mal :P, mas obrigada!!

 

Quando der um tempo vou postar um exemplo a partir do seu programa