int i;
for (i = 0; i < tam; i++) {
printf("%5d ", a[i]);
}
printf("\n\n");
}
int gerarNumeroAleatorio(int max) {
return rand() % max;
}
void trocarValores(int *a, int i, int j) {
int aux;
aux = a[i];
a[i] = a[j];
a[j] = aux;
}
void exibirPorcentagem(int i, int tam) {
if (i % (tam / 100) == 0)
printf("%d %\n", i);
}
void merge(int pivot, int low, int length, int high, int* a) {
int merge1, merge2, i, *working;
merge1 = 0;
merge2 = pivot - low + 1;
working = (int*) malloc(length * sizeof(int));
for (i = 0; i < length; i++){
working[i] = a[low + i];
}
for (i = 0; i < length; i++) {
// iterando dentro de cada subvetor
if (merge2 <= high - low) {
if (merge1 <= pivot - low) {
if (working[merge1] > working[merge2]) {
a[i + low] = working[merge2++];
} else {
a[i + low] = working[merge1++];
}
} else {
a[i + low] = working[merge2++];
}
} else {
a[i + low] = working[merge1++];
}
}
}
void mergesort(int *a, int low, int high) {
int i = 0;
int length = high - low + 1;
int pivot = 0;
int * working;
if (low == high) // caso base: vetor de tamanho 1
return;
pivot = (low + high) / 2; // cálculo do ponto médio
mergesort(a, low, pivot); // dividir a esquerda
mergesort(a, pivot + 1, high); // dividir a direita
merge(pivot, low, length, high, trocas, a); // junção das soluções
}
void quicksort(int *a, int tam, int left, int right) {
int i, j, p;
i = left;
j = right;
p = a[(left + right) / 2]; // Elemento intermediário como “pivo”
do {
while (a[i] < p && i < right)
i++;
while (a[j] > p && j > left)
j--;
if (i <= j) {
trocarValores(a, i, j);
trocas++;
i++;
j--;
}
exibirPorcentagem(i, tam);
} while (i <= j);
if (left < j)
quicksort(a, tam, left, j);
if (i < right)
quicksort(a, tam, i, right);
}
void bubbleSort(int *a, int tam) {
int i, j;
unsigned long trocas = 0;
for (i = 0; i < tam; i++) {
for (j = 0; j < tam - 1; j++) {
if (a[j] > a[j + 1]) {
trocarValores(a, j, j + 1);
trocas++;
}
}
}
}
void insertionSort(int *a, int tam) {
int i, iHole, item;
for (i = 1; i < tam; i++) {
// A[ i ] is added in the sorted sequence A[0, .. i-1]
// save A[i] to make a hole at index iHole
item = a[i];
iHole = i;
// keep moving the hole to next smaller index until A[iHole - 1] is <= item
while (iHole > 0 && a[iHole - 1] > item) {
// move hole to next smaller index
a[iHole] = a[iHole - 1];
iHole = iHole - 1;
}
// put item in the hole
a[iHole] = item;
exibirPorcentagem(i, tam);
}
}
void selectionSort(int * a, int tam) {
int i, j, menor; // declaração de variáveis
// percorrer todas as posições do vetor, um a um
for (i = 0; i < tam; i++) {
menor = i; // assumir que o primeiro no intervalo é menor
// percorrer o vetor para buscar alguem menor, caso exista
for (j = i + 1; j < tam; j++) { // se for menor que o menor encontrado
if (a[j] < a[menor]) { // anote-o
menor = j;
}
} // se alguem menor que o menor for encontrado
if (menor != i) { // trocar as posições dos dois
trocarValores(a, menor, i);
}
exibirPorcentagem(i, tam);
}
}
void copy(int *b, int *a, int tam) {
int i = 0;
for (i = 0; i < tam; i++) {
a[i] = b[i];
}
}
/*
============================================================================
Name : Projeto-pa-ordenacao2.c
Author :
Version :
Copyright : Your copyright notice
Description : Hello World in C, Ansi-style
============================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "ordenacao.h"
int main(void) {
int *a, *b, tam, i, num, lim;
time_t seconds, start, end;
double duration;
unsigned long trocas = 0;
tam = 1000000000;
lim = 100000;
time(&seconds);
srand((unsigned int) seconds);
//printf("Digite o tamanho do vetor:");
//scanf("\n%d", &tam);
a = (int*) malloc(tam*sizeof(int));
b = (int*) malloc(tam*sizeof(int));
for (i = 0; i < tam; i++)
{
num = gerarNumeroAleatorio(lim);
a[i] = num;
b[i] = num;
}
// time(&start);
// trocas = selectionSort(a, tam);
// time(&end);
// duration = difftime(end, start);
// printf("\nDuration: %f seconds \tTrocas: %u\n", duration, trocas);
// system("PAUSE");
// copy(b, a, tam);
// time(&start);
// trocas = insertionSort(a, tam);
// time(&end);
// duration = difftime(end, start);
// printf("\nDuration: %f seconds \tTrocas: %u\n", duration, trocas);
// system("PAUSE");
// copy(b, a, tam);
// time(&start);
// trocas = bubbleSort(a, tam);
// time(&end);
// duration = difftime(end, start);
// printf("\nDuration: %f seconds \tTrocas: %u\n", duration, trocas);
// system("PAUSE");
// copy(b, a, tam);
time(&start);
trocas = quicksort(a, tam, 0, tam-1);
time(&end);
duration = difftime(end, start);
printf("\nDuration: %f seconds \tTrocas: %u\n", duration, trocas);
system("PAUSE");
copy(b, a, tam);
time(&start);
trocas = mergesort(a, 0, tam-1);
time(&end);
duration = difftime(end, start);
printf("\nDuration: %f seconds \tTrocas: %u\n", duration, trocas);
system("PAUSE");
return EXIT_SUCCESS;
}
Nenhum comentário:
Postar um comentário