C programa utilizando função Randon.

Natal junio · 3 de abril de 2020

Então preciso construir um programa em C, que:

–O usuário escolhe o tamanhos do vetor ((a)5!, (b)10!, (c)15!, (d) 20! ou (e) 25!).

–Após a escolha do tamanho, o vetor é preenchido utilizando função Randon.

–O programa deve:

•Ordenar uma cópia deste vetor original para cada método de ordenação.

•Contar quantas comparações e trocas são feitas, e o tempo em ms gasto por cada método de ordenação.

queria saber se tem como usar o seguinte codigo que fiz, caso alguem consiga também poderia me ajudar.?

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

#define m 1000
#define k 10000
#define o 100000
#define p 400000
#define true 1

void insertionSort(int vet[ ],int n)
{
	int i,j,aux;
	for (i=1; i<n; i++)
	{
		aux = vet[i];
		
		for(j=i-1; j>=0 && vet[j] > aux; j--)
		{
			vet[j+1]=vet[j];
		}
		vet[j+1]=aux;
	}
}

void mergeSort(int vetor[], int tamanho){
	
  int meio = tamanho / 2;
  int i = 0;
  int j = meio;
  int t = 0;
  int aux[tamanho];
  
	while( i < meio && j < tamanho ){
	    if( vetor[i] <= vetor[j] )
	    	aux[t] = vetor[i++];
	    else
	    	aux[t] = vetor[j++];
	    t++;
	}
 
	if( i == meio ){
    	while( j < tamanho ){
            aux[t] = vetor[j++];
            t++;
      }
	}else {
    	while( i < meio ){
            aux[t] = vetor[i++];
            t++;
    	}
	}
	
	for( i = 0; i < tamanho; i++ ){
    	vetor[i] = aux[i];
	}
}

int mergeSortRec(int vetor[], int tamanho)
{
	int meio = tamanho / 2;

	if( tamanho > 1 ){
		mergeSortRec(vetor, meio);
		mergeSortRec(vetor + meio, tamanho - meio);
		mergeSort(vetor, tamanho);
	}
}

void selectionSort(int vet[], int tam){
	
	int i, j, eleito, menor, pos;
	
	for(i=0; i<=tam; i++){
		eleito = vet[i];
		menor = vet[i+1];
		pos = i+1;
		
		for(j=i+1; j<=tam; j++){
			if(vet[j] < menor){
				menor = vet[j];
				pos = j;
			}
		}
		
		if(menor < eleito){
			vet[i] = vet[pos];
			vet[pos] = eleito;
		}
	}
}

void bubbleSort(int vet[], int tam){
	
	int i, n, aux;
	int troca;
	
	troca = 1;
	
	while (n < tam && troca == 1){
		troca = 0;
		
		for(i=0; i<tam; i++){
			if(vet[i] > vet[i+1]){
				troca = 1;
				aux = vet[i];
				vet[i] = vet[i+1];
				vet[i+1] = aux;
			}	
		}
		
		n = n+1;
	}
}

void quickSort(int vet[], int esq, int dir) {
    
	int i, j, pivo, aux;
	int qtd;
     
    i = esq;
    j = dir;
    
    pivo = vet[(esq + dir) / 2];
    
    while(i <= j) {
    	
        while(vet[i] < pivo && i < dir) {
            i++;
        }
        
        while(vet[j] > pivo && j > esq) {
            j--;
        }
        
        if(i <= j) {
            aux = vet[i];
            vet[i] = vet[j];
            vet[j] = aux;
            i++;
            j--;
        }
    }
    
    if(j > esq) {
        quickSort(vet, esq, j);
    }
    if(i < dir) {
        quickSort(vet, i, dir);
    }
}

void heapSort(int a[], int n) {
	
	int i = n / 2, pai, filho, t;
   
	while(true) {
   	
		if (i > 0) {
			i--;
        	t = a[i];
    	} else {
			n--;
          	if (n <= 0) return;
          	
          	t = a[n];
          	a[n] = a[0];
      	}
      	
		pai = i;
		
      	filho = i * 2 + 1;
      	
		while (filho < n) {
        	if ((filho + 1 < n)  &&  (a[filho + 1] > a[filho]))
              	filho++;

          	if (a[filho] > t) {
             	a[pai] = a[filho];
             	pai = filho;
             	filho = pai * 2 + 1;
          	} else {
            	break;
        	}
      }
      
	  a[pai] = t;
   }
}

zerarVetor(int vet[], int vetCopy[], int tam){
	int i;
	for(i = 0; i < tam; i++){
		vetCopy[i] = vet[i];
	}
}

imprimiVetor(int vet[], int tam){
	int i;
	printf("Vetor: ");
	for(i = 0; i < tam; i++){
		printf("[%d] ",vet[i] );
	}
}

int existe(int valores[], int tam, int valor){
	int i;
	
	for(i=0; i<tam; i++){
		if(valores[i]==valor){
			return 1;
		}
	}
	return 0;
}

void geraAleatorio(int num[], int quant, int limite){
	
	int i, val;
	
	for(i=0; i<quant; i++){
		
		val = rand() % limite;
		
		while(existe(num, i, val)){ 
			val = rand() % limite;
		}
		num[i] = val;
	}
}

calcula(int tam){	
	int i;
	//vetores originais
	int *vet = (int *) malloc(tam * sizeof(int));
	
	//vetores copidas, para que assim sempre seja ordenado os memos números
	int *vetCopy = (int *) malloc(tam * sizeof(int));
	
	//variaveis para calcular o tempo
 	LARGE_INTEGER tempoInicial, tempoFinal, freq;
 	float tempoTotal;	
	
	//preencer vetores de 1000
	geraAleatorio(vet,tam,(tam+1));
		
	zerarVetor(vet, vetCopy, tam);
		
	//calcular tempo de ordenação para vetores tamanho m, k, o ou p.
	//m = 1000   |    k = 10000   |     o = 100000    |    p = 400000
	
	srand(time(NULL));
	QueryPerformanceCounter(&tempoInicial);
	insertionSort(vetCopy,tam);
	QueryPerformanceCounter(&tempoFinal);
	QueryPerformanceFrequency(&freq);
	tempoTotal = (float)(tempoFinal.QuadPart - tempoInicial.QuadPart)/freq.QuadPart;
					 			
	printf("Insertion Sort: %f ms", tempoTotal);
	printf("\n");
	zerarVetor(vet, vetCopy, tam);
				    			
	srand(time(NULL));
	QueryPerformanceCounter(&tempoInicial);
	selectionSort(vetCopy,tam);
	QueryPerformanceCounter(&tempoFinal);
	QueryPerformanceFrequency(&freq);
	tempoTotal = (float)(tempoFinal.QuadPart - tempoInicial.QuadPart)/freq.QuadPart;
					 			
	printf("Selection Sort: %f ms", tempoTotal);
	printf("\n");
	zerarVetor(vet, vetCopy, tam);
				    			
	srand(time(NULL));
	QueryPerformanceCounter(&tempoInicial);
	mergeSortRec(vetCopy,tam);
	QueryPerformanceCounter(&tempoFinal);
	QueryPerformanceFrequency(&freq);
	tempoTotal = (float)(tempoFinal.QuadPart - tempoInicial.QuadPart)/freq.QuadPart;
					 			
	printf("Merge Sort: %f ms", tempoTotal);
	printf("\n");
	zerarVetor(vet, vetCopy, tam);
				    			
	srand(time(NULL));
	QueryPerformanceCounter(&tempoInicial);
	heapSort(vetCopy,tam);
	QueryPerformanceCounter(&tempoFinal);
	QueryPerformanceFrequency(&freq);
	tempoTotal = (float)(tempoFinal.QuadPart - tempoInicial.QuadPart)/freq.QuadPart;
					 			
	printf("Heap Sort: %f ms", tempoTotal);
	printf("\n");
	zerarVetor(vet, vetCopy, tam);
				    			
	srand(time(NULL));
	QueryPerformanceCounter(&tempoInicial);
	bubbleSort(vetCopy, tam);
	QueryPerformanceCounter(&tempoFinal);
	QueryPerformanceFrequency(&freq);
	tempoTotal = (float)(tempoFinal.QuadPart - tempoInicial.QuadPart)/freq.QuadPart;
					 			
	printf("Bubble Sort: %f ms", tempoTotal);
	printf("\n");
	zerarVetor(vet, vetCopy, tam);
				    			
	srand(time(NULL));
	QueryPerformanceCounter(&tempoInicial);
	quickSort(vetCopy, 0, tam-1);
	QueryPerformanceCounter(&tempoFinal);
	QueryPerformanceFrequency(&freq);
	tempoTotal = (float)(tempoFinal.QuadPart - tempoInicial.QuadPart)/freq.QuadPart;
					 			
	printf("Quick Sort: %f ms", tempoTotal);
	printf("\n");
	
	zerarVetor(vet, vetCopy, tam);	
	
	free(vet);
	free(vetCopy);
}

int main()
{
	setlocale (LC_ALL, "");
			
	//m = 1000   |    k = 10000   |     o = 100000    |    p = 400000  
					
	printf("Tempo de Exeução em Milissegundos");
	
	printf("\n\nCom 1000 números:\n\n");
	printf("calculando ... Aguarde...\n\n");
	calcula(m);
	
	printf("\n\nCom 10000 números:\n\n");
	printf("calculando ... Aguarde...\n\n");
	calcula(k);
	
	printf("\n\nCom 100000 números:\n\n");
	printf("calculando ... Aguarde...\n\n");
	calcula(o);
	
	printf("\n\nCom 400000 números:\n\n");
	printf("calculando ... Aguarde...\n\n");
	calcula(p);
	
	printf("\n\n");
	system("pause");
	return 0;
}

arfneto · 3 de abril de 2020

Não vejo porque não poderia usar esse código.

As rotinas de classificação já estão funcionando? Se estão não precisa claro ficar compilando toda hora tudo isso, certo?

E se não estão é melhor não seguir adiante com métodos não testados.

Mas você vai ter que inserir código nesses métodos para contar as inversões e comparações. E dependendo do método isso não é assim tão importante. Esse programa não é assim muito útil a menos que se escolha bem o que se está comparado... Recursivo? In-place? Coisas assim. Mas não importa aqui.

Porque chama srand(time(NULL)) a toda hora? Não é necessário. Na verdade não deveria usar esse parâmetro. Use uma única vez e com algo conhecido quando quiser reproduzir a sequência... E vai querer para que as condições de comparação sejam justas.

Como o custo de copiar o vetor é muito menor que o de gerar outras cópias, devia simplesmente gerar um vetor e usar esse para alimentar TODOS os testes ou não adianta comparar nada.