C++ Funcções por ordenação para vetores de valores inteiros

Wesley Araujo Fernandes · 23 de maio de 2022

Escreva três funções em C que implemente os seguintes algoritmos de ordenação para vetores de valores inteiros:

> por inserção (insertion sort)

> ordenação por intercalação (merge sort)

> ordenação rápida (quick sort)

Em seguida, escreva uma função main para testar a sua implementação. Implemente um código para fazer uma análise do desempenho das três funções acima com 10 vetores de tamanhos diferentes entrada de dados. Exiba os resultados de tempo de cada algoritmo para cada vetor em um arquivo benchmark.tsv, e explique os resultados em termos da complexidade no pior caso de cada algoritmo.

alguém me explique com palavras mais claras o que eu preciso fazer aqui, confesso que não entendi bem

devair1010 · 24 de maio de 2022

@Wesley Araujo Fernandes faz parte do exercício interpretar o enunciado , os métodos de Ordenação de vetores exstem muitos mesmos , e ali está pedindo apenas três , que são os mis conhecidos , e uma função para cada um , e então faça um código e poste ele aqui e ajudaremos .

Leotanis Leite Moraes · 24 de maio de 2022

1 - fazer uma funcao principal do programa, para ele iniciar, no caso int main return 0 no final, padraozim.

2 - declarar 10 vetores de numeros inteiros, e codigo para ler eles do usuario.

3 - fazer 3 funcoes (metodo, pode ser sem retorno) que vai ordenar estes vetores (uma para cada enunciada).

4 - Imagino que este arquivo vai ser gerado pelo compilador quando execetuar seu programa, da ide que estiver usando, e o anunciado te pede para analisar os dados fornecidos neste arquivo.

arfneto · 24 de maio de 2022

3 horas atrás, Wesley Araujo Fernandes disse:

alguém me explique com palavras mais claras o que eu preciso fazer aqui, confesso que não entendi bem

tem várias coisas pra você fazer aí nessa lista. Porque não faz algumas antes de se preocupar com o todo?

Escreveu as funções de ordenação ao menos???

Alguma função de leitura?

Alguma para mostrar o vetor já que obviamente vai querer mostrar antes e depois de ordenar?

Alguma para medir o intervalo? Sabe que vai precisar disso então se pudesse marcar o tempo entre uma leitura e outra por exemplo já estaria no caminho certo.

devair1010 · 24 de maio de 2022

@Wesley Araujo Fernandes e essa parte do enunciado diz , Exiba os resultados de tempo de cada algoritmo para cada vetor em um arquivo benchmark.csv, , e então você pode usar o comado "clock_t tempo;" , junto com a função "clock();"" , para determinar o tempo gasto , como bem explicado messe tópico :

https://www.clubedohardware.com.br/forums/topic/1031279-resolvido-medir-tempo-de-execução-em-c/

Wesley Araujo Fernandes · 30 de maio de 2022

fiz uns exemplos das funções que esta pedindo, porém não consigo juntas as tres funções dentro de uma algoritmo so, alguém pode me ajudar nisso, e também a respeito dessa marcação de tempo

void merge(int arr[], int l, int m, int r)
{
   int i, j, k;
   int n1 = m - l + 1;
   int n2 = r - m;

int L[n1], R[n2]; //criando matrizes temporarias

   //copie dados para matrizes temporarias L e R

   for (i = 0; i < n1; i++)
       L[i] = arr[l + i];
   for (j = 0; j < n2; j++)
       R[j] = arr[m + 1 + j];

   //mesclar as matrizes temporarias de volta no arr

   i = 0;                                                       //variavel inicial da primeira submatriz
   j = 0;                                                       //variavel inicial da segundo submatriz
   k = l;                                                       //variavel inicial da mesclado submatriz
   while (i < n1 && j < n2) {
       if (L[i] <= R[j]) {
           arr[k] = L[i];
           i++;
       }
       else {
           arr[k] = R[j];
           j++;
       }
       k++;
   }

   while (i < n1) {                                           //Copie os elementos restantes de R, se houver algum
       arr[k] = L[i];
       i++;
       k++;
   }

   while (j < n2) {                                           //Copie os elementos restantes de R, se houver algum
       arr[k] = R[j];
       j++;
       k++;
   }
}

void mergeSort(int arr[], int l, int r) //L é para o indice esquerdo e R é o indice direito da submatriz de arr a ser classificado
{
   if (l < r) {
       // Same as (l+r)/2, but avoids overflow for
       // large l and h
       int m = l + (r - l) / 2;

       // Sort first and second halves
       mergeSort(arr, l, m);
       mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}

void printArray(int A[], int size)
{
   int i; //funções de utilidade
   for (i = 0; i < size; i++) //função para imprimir uma matriz
       printf("%d ", A[i]);
   printf("\n");
}

int main()                                                   //chamada da função de acordo com os numeros desejados pelo usuario
{
   int arr[] = { 80, 60, 20, 10, 6, 7 };
   int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("A matriz dada e: \n");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

   printf("\nA matriz ordenada e: \n");
   printArray(arr, arr_size);
   return 0;
}

essa e a merge sort, falta as outras 2 duas funções para juntar com essa, alguém me da ess luz

arfneto · 30 de maio de 2022

Use o tal botão code, como explicado no primeiro post deste forum.

Veja a diferença:

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];                                            //criando matrizes temporarias

    //copie dados para matrizes temporarias L e R
    
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    //mesclar as matrizes temporarias de volta no arr
    
    i = 0;                                                        //variavel inicial da primeira submatriz
    j = 0;                                                        //variavel inicial da segundo submatriz
    k = l;                                                        //variavel inicial da mesclado submatriz
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {                                            //Copie os elementos restantes de R, se houver algum
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {                                            //Copie os elementos restantes de R, se houver algum
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r)                        //L é para o indice esquerdo e R é o indice direito da submatriz de arr a ser classificado
{
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l + (r - l) / 2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

void printArray(int A[], int size)
{
    int i;                                                     //funções de utilidade
    for (i = 0; i < size; i++)                                //função para imprimir uma matriz
        printf("%d ", A[i]);
    printf("\n");
}

int main()                                                    //chamada da função de acordo com os numeros desejados pelo usuario
{
    int arr[] = { 80, 60, 20, 10, 6, 7 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("A matriz dada e: \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nA matriz ordenada e: \n");
    printArray(arr, arr_size);
    return 0;
}

Poste um código completo, compilável. Isso inclui os headers, de modo que quem queira e possa ajudar tenha condição de copiar o código direto do formulário de código para o IDE sem ter que ficar completando...

Em relação aos tempos, você deve claro redefinir o vetor para ficar igualzinho entre cada chamada das 3 rotinas de sort. E para marcar o tempo simplesmente salve a hora de início e fim e subtraia para cada uma e coloque numa tabela. time() retorna a hora.

agora, arfneto disse:
int L[n1], R[n2];

Isso não funciona em C. Até existe em programas de estudantes e um ou outro lugar um trem chamado VLA mas não é algo a ser levado a s;erio, eu acho.

Declare o vetor com um certo tamanho, conhecido em tempo de compilação, ou use alocação dinâmica e aloque um ao saber o tamanho necessário.

Em 23/05/2022 às 20:51, Wesley Araujo Fernandes disse:

alguém me explique com palavras mais claras o que eu preciso fazer aqui, confesso que não entendi bem

No seu livro deve estar a discussão sobre esses métodos de classificação e lá tem o pior caso para cada um deles.

Como pode ser que o pior caso de um não seja o pior caso de outro você pode ter até 3 casos diferentes...

Para esses casos você vai pegar o mesmo vetor e classificar pelos 3 métodos, marcando o tempo gasto em cada um.

Depois vai gravar isso numa tabela.

Era o que tinha imaginado?

17 minutos atrás, Wesley Araujo Fernandes disse:

fiz uns exemplos das funções que esta pedindo, porém não consigo juntas as tres funções dentro de uma algoritmo so

Não vai juntar em um algoritmo só. Vai comparar as 3...

Wesley Araujo Fernandes · 30 de maio de 2022

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <locale.h>
#include <time.h>

void insertionsort(int n, int v[]);
int part (int n, int f, int v[]);
void quicksort(int i, int f, int v[]);
int *Ler(int n);
int main(){
	
	setlocale(LC_ALL,"");
	clock_t tempos[2];
	tempos[0] = clock();
	tempos[1] = clock();
	int n;
	printf("\nInforme um valor para a quantidade de elementos: ");
	scanf("%i", &n);
	printf("\nVetor 1:\n");
	int *v1 = Ler(n);
	printf("\nVetor 2:\n");
	int *v2 = Ler(n);
	printf("\nVetor 3:\n");
	int *v3 = Ler(n);
	printf("\nVetor 4:\n");
	int *v4 = Ler(n);
	printf("\nVetor 5:\n");
	int *v5 = Ler(n);
	printf("\nVetor 6:\n");
	int *v6 = Ler(n);
	printf("\nVetor 7:\n");
	int *v7 = Ler(n);
	printf("\nVetor 8:\n");
	int *v8 = Ler(n);
	printf("\nVetor 9:\n");
	int *v9 = Ler(n);	
	printf("\nVetor 10:\n");
	int *v0 = Ler(n);
	int i;
	
	FILE *arch = fopen("benchmark.tsv","w");
	
	//Chamada e ordenação por quicksort
	
	printf("\n=======QUICKSORT EXECUTADO=====\n");
	quicksort(0, n - 1, v1);
	quicksort(0, n - 1, v2);
	quicksort(0, n - 1, v3);
	quicksort(0, n - 1, v4);
	quicksort(0, n - 1, v5);
	quicksort(0, n - 1, v6);
	quicksort(0, n - 1, v7);
	quicksort(0, n - 1, v8);
	quicksort(0, n - 1, v9);
	quicksort(0, n - 1, v0);
	
	double T[2];
	
	T[0] = (tempos[0] - tempos[1])*1000/CLOCKS_PER_SEC;
	
	fprintf(arch,"\nTempo de execução do quicksort: %g ms.\n", T[0]);
	printf("\n======INSERTIONSORT EXECUTADO======\n");
	insertionsort(n,v1);
	insertionsort(n,v2);
	insertionsort(n,v3);
	insertionsort(n,v4);
	insertionsort(n,v5);
	insertionsort(n,v6);
	insertionsort(n,v7);
	insertionsort(n,v8);
	insertionsort(n,v9);
	insertionsort(n,v0);
	
	T[1] = (tempos[0] - tempos[1])*1000/CLOCKS_PER_SEC;
	
	fprintf(arch,"\nTempo de execução do insertionsort: %g ms.\n", T[1]);
	
	printf("\nPrograma finalizado!\n");
	fclose(arch);
	system("pause");
	printf("\n\n");
	return 0;
}

int *Ler(int n){
	int i;
	int *v = (int*)malloc(n*sizeof(int));
	for(i = 0; i < n; i++){
		printf("\nInsira o valor da posição %i do vetor: ", i+1);
		scanf("%i", &v[i]);
	}
	
	return v;
}

void insertionsort(int n, int v[n]){

	int i, j;
	//Ordenação por inserção
	//O indice i inicia na posição 1 do vetor, ou seja, a segunda posição do vetor. Já j inicia no indice i - 1, ou seja, inicialmente na primeira
	//posição do nosso vetor
	for(i = 1; i < n; i++){
		int x = v[i]; //Pegamos o valor atual a qual vai ser ordenado do vetor na posição i e o guardamos em uma variavel auxiliar
		
		//j sempre estará na posição atrás do indice i
		for(j = i - 1; j>= 0 && x < v[j]; j--){
			v[j+1] = v[j]; //aqui é onde ocorre uma parte da ordenação, onde trocamos o valor de j = i - 1 pelo valor de i, caso este seja menor que o valor de j
		}
		v[j+1] = x; //Para que não fiquemos com valores iguais em duas posições do vetor, atribuimos o valor de i guardado em x a posição que 
					//anteriormente foi do menor valor encontrado
	}
}

int part (int n, int f, int v[]){
	
	int piv = v[f]; //atribuindo o valor que está na posição final do vetor a variavel que serve para comparação de valores
	int j = n - 1; // atribuindo o valor inicial a variavel contadora - 1, por termos de posição de vetor
	int i; //variavel contadora
	for(i = n; i < f; i++){
		if (v[i]<= piv){
			j++;
			int temp = v[j]; //Guardando valor que foi encontrado a qual é menor que piv em uma variavel temporaria
			v[j] = v[i]; //Atribuindo ao valor inicial, na posição correta o menor valor encontrado comparado ao valor na posição final do vetor (piv) 
			v[i] = temp; //Atribuindo o valor que foi trocado de posição, o valor que anteriormente foi o menor valor encontrado na posição j
		}
	}
	//Aqui realizamos a troca do valor que estava na posição final do vetor,
	//a qual será inserido na sua posição correta, onde todos os elementos a sua direita são maiores e a esquerda estão os menores que ele
	int temp = v[j + 1];  
	v [j+1] = v[f];
	v[f] = temp;
	return j+1; //Retornando a posição do piv
}

void quicksort (int i, int f, int v[]){
	//caso o inicio seja menor que o final, realizamos o quick sort
	if (i < f){
		int p = part(i, f, v); //Recebendo valor retornado da função que realiza a ordenação. A cada rodada ele inicia ordena do inicio para o meio e do meio para o fim
		quicksort(i, p-1, v); //Ordenando os valores do inicio ao meio
		quicksort(p+1, f, v); //Ordenando os valores do meio ao fim
	}
}

coloquei as duas funções, falta esse merge, mais to perdido pra adicionar ela, alguém junta ai por favor kk ou me e ensina

é uma coisa que queria otimizar nesse meu code era os vetores, declarei 10 e ficou mt extenso, como faço pra otimizar isso?

arfneto · 31 de maio de 2022

int *Ler(int n){
	int i;
	int *v = (int*)malloc(n*sizeof(int));
	for(i = 0; i < n; i++){
		printf("\nInsira o valor da posição %i do vetor: ", i+1);
		scanf("%i", &v[i]);
	}
	
	return v;
}

Não escreva nunca um programa interativo se puder evitar. Só vai perder tempo.

Nesse caso aqui não consegui entender o sentido.

Vai usar 10 vetores para que?

E porque vai ler isso do teclado? Vai levar uma semana para cada teste do programa?

No primeiro post tinha um Merge sem as outras funções e sem marcar o tempo. Agora tem um programa que marca o tempo e tem duas funções de sort mas o merge sumiu e não sabe como colocar mesmo tempo postado hoje mesmo a função?

E sobre Ler() ela retorna um ponteiro. Não vi uma única chamada a free() no código. Como vai liberar isso?

Entenda que Ler é uma função e retorna algo. Nesse caso retorna int*. É isso que está lá delcarado. Para o compilador C não faz diferença como escreve isso, mas para você e outros que venham a ler o programa entenda que em C se declara um nome e um tipo. Nesse caso o nome é Ler e o tipo é int*(), uma função que retorna um ponteiro para um int.

Sugiro sempre escrever

    int*                  Ler()

E nunca

    int                            *Ler()

Ler é int*() e assim é claro que *Ler() é int, mas isso é consequência e não a declaração.

Postei um programa aqui tempos atrás que faz isso, chama 3 funções para fazer a mesma coisa e compara os tempos. Talvez você possa dar uma olhada. É exatamente o que você precisa fazer.

Essa função faz o serviço:

clock_t testa_funcao(unsigned n, char (*F)(char[9]))
{
    char    linha[20];
    for (int d = 0; d < 9; d += 1) linha[d] = '0' + rand() % 10;
    clock_t inicio = clock();
    for (unsigned i = 0; i < n; i += 1) (*F)(linha);
    clock_t fim = clock();
    return (fim - inicio);
}