Código da Aula de EDA dia 27-09-2011

Spoiler:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h> // Utilizada na função Random para modificar a "semente"
#include <windows.h> //Utilizada para a função de medição do tempo gasto do algoritmo
#include <winbase.h> //Também utilizada para a função de medição do tempo gasto do algoritmo

#define N 100000


int particiona(int *vet, int inicio, int fim)
{
int i, aux, pivo, temp;

aux = inicio-1;
pivo = vet[fim];

for(i=inicio; i<=fim; i++)
{
if(vet[i] <= pivo)
{
aux++;
temp = vet[i];
vet[i] = vet[aux];
vet[aux] = temp;
}
}

return aux;
}

void quick(int *vet, int inicio, int fim)
{
int p;

if(inicio < fim)
{
p = particiona(vet,inicio,fim);
quick(vet,inicio,p-1);
quick(vet,p+1,fim);
}
}

void sel(int *vet, int inicio, int fim)
{
int i, maior, temp;

while(inicio < fim)
{
maior = fim;
for(i = inicio; i < fim; i++)
{
if(vet[i] > vet[maior])
{
maior = i;
}
}
if(maior != fim)
{
temp = vet[maior];
vet[maior] = vet[fim];
vet[fim] = temp;
}
fim--;
}
}

int main(int argc, char** argv)
{
int vet[N], i;

//(lp vem de Long Pointer)

LARGE_INTEGER lpInicio, lpFim, lpFrequencia, tempo; //Define as variáveis como o tipo LARGE_INTEGER pertencente a uma das bibliotecas <windows.h> ou <winbase.h>

QueryPerformanceFrequency(&lpFrequencia); //Passa a variável lpFrequencia por referencia, guardando na mesma o valor obtido da frequencia do timer do sistema

printf("Pressione uma tecla para iniciar");
getch();

printf("Ordenando...Aguarde");

QueryPerformanceCounter(&lpInicio); //Inicia a contagem, guardando na variavel lpInicio o valor corrente do timer do sistema

srand(time(NULL)); //Muda a semente do aleatório.

for(i=0; i<N; i++)
{
vet[i] = rand() % 100000;
}

sel(vet,0,N);
//quick(vet,0,N);

QueryPerformanceCounter(&lpFim); //Termina a contagem, guardando na variavel lpFim o valor corrente do timer do sistema

tempo.QuadPart = (lpFim.QuadPart - lpInicio.QuadPart); //Subtrai o tempo final do inicial


// for(i=0; i<N; i++)
// {
// printf("%d ",vet[i]);
// }
// printf("\n");

printf("\nTerminado. Tempo gasto: %.9f",(float) ((float)tempo.QuadPart / (float)lpFrequencia.QuadPart)); //Divide pela frequencia do timer, mostrando o tempo em segundos
getch();

return 0;
}

/ Create Threads.cpp : Defines the entry point for the console application.
//

#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <time.h>

#define N 100000
#define RANGE 10000

void sel(unsigned int *vet, unsigned int inicio, unsigned int fim)
{
unsigned int i, maior, temp;

while(inicio < fim)
{
maior = fim;
for(i = inicio; i < fim; i++)
{
if(vet[i] > vet[maior])
{
maior = i;
}
}
if(maior != fim)
{
temp = vet[maior];
vet[maior] = vet[fim];
vet[fim] = temp;
}
fim--;
}
}

unsigned int particiona(unsigned int *vet, unsigned int inicio, unsigned int fim)
{
unsigned int i, aux, pivo, temp;

aux = inicio-1;
pivo = vet[fim];

for(i=inicio; i<=fim; i++)
{
if(vet[i] <= pivo)
{
aux++;
temp = vet[i];
vet[i] = vet[aux];
vet[aux] = temp;
}
}

return aux;
}

void quick(unsigned int *vet, unsigned int inicio, unsigned int fim)
{
unsigned int p;

if(inicio < fim)
{
p = particiona(vet,inicio,fim);
quick(vet,inicio,p-1);
quick(vet,p+1,fim);
}
}

void merge(unsigned int *vet1, unsigned int inicio, unsigned int fim)
{
unsigned int *aux, *vet2, i, j, k, qtd, qtd1, qtd2;

vet1 = vet1 + inicio;
qtd = fim - inicio + 1;
aux = (unsigned int*) malloc(sizeof(unsigned int) * qtd ); // Alocando buffer auxiliar para intercalar
qtd1 = qtd/2; // O primeiro vetor tera a metade dos elementos do vetor original

//fim1 = inicio + qtd1;

vet2 = vet1 + qtd1; // O vetor vet2 comeca no endereco vet + qtd1
qtd2 = qtd-qtd1; // A quantidade de elementos em vet2 é a quantidade total - qtd1

// Intercalar:

i = j = k = 0; // i = indice de vet1, j = indice de vet2, k = indice de aux
while(i < qtd1 && j < qtd2)
{
if(vet1[i] < vet2[j])
{
aux[k] = vet1[i];
i++;
}
else
{
aux[k] = vet2[j];
j++;
}
k++;
}

// Aqui alguem acabou quem não acabaou tem que ser copiado para aux.

while(i < qtd1)
{
aux[k] = vet1[i];
i++;
k++;
}

while(j < qtd2)
{
aux[k] = vet2[j];
j++;
k++;
}

// Vetor intercalado em aux. Copiar os elementos para vet1. Poderia ser com for, mas assim é melhor:

memcpy(vet1,aux,sizeof(int)*qtd);

// Nao precisamos mais do aux

free(aux);

}

void imprime_vetor(unsigned int *vet)
{
int i;
printf("\n\nVetor:");

for (i=0; i<N; i++)
printf (" %d ",vet[i]);
}

void preenche_vetor(unsigned int *vet)
{
unsigned int i;

for(i=0; i<N; i++) //Gera os números aleatórios e preenche o vetor
{
vet[i] = rand() % RANGE;
}
}

DWORD SelectionThreadProc (LPVOID lparam );
DWORD MergeThreadProc (LPVOID lpParam );
DWORD MainThreadProc(LPVOID lpParam );

typedef struct
{
unsigned int inicio;
unsigned int fim;
unsigned int *vet;
unsigned int pMask;
unsigned int intervalo;
} DADOS;

int main()
{
unsigned int *vet;

DADOS *d; //Variavel para alocação dinamica do inicio e fim, que serão passados por referencia ao Merge

LARGE_INTEGER lpInicio, lpFim, lpFrequencia, tempo; //Variáveis para cálculo do tempo

DWORD dwThreadId;
HANDLE hMainThread;

vet = (unsigned int*) malloc(sizeof(unsigned int) * N);

QueryPerformanceFrequency(&lpFrequencia);
printf("Pressione uma tecla para começar a ordenar");
getch();

printf("\nIniciado...Aguarde");

srand(time(NULL)); //Muda a semente do aleatório.

preenche_vetor(vet);

QueryPerformanceCounter(&lpInicio);

d = (DADOS*) malloc(sizeof(DADOS));
d->inicio = 0;
d->fim = N - 1;
d->vet = vet;

hMainThread = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&MainThreadProc, (LPVOID) d, 0, &dwThreadId);
WaitForSingleObject(hMainThread,INFINITE);
QueryPerformanceCounter(&lpFim);
tempo.QuadPart = (lpFim.QuadPart - lpInicio.QuadPart);
printf("\nTempo gasto: %.9f", (float) tempo.QuadPart / lpFrequencia.QuadPart);

CloseHandle(hMainThread);
free(d);
free(vet);
//imprime_vetor(vet);

getch();
return 0;
}

//Thread Routine
DWORD SelectionThreadProc (LPVOID lpParam ) //Thread que executa o selection
{
DADOS *d;

d = (DADOS*) lpParam;

sel(d->vet,d->inicio, d->fim);
return 0;
}

DWORD MergeThreadProc (LPVOID lpParam ) //Thread que executa a intercalação
{
int i, nThreads=2, ThreadNum,tempMask;
unsigned int intervalo;

DADOS *d, aux[2];
HANDLE *hThreadArray;
DWORD dwThreadId;

d = (DADOS*) lpParam;
intervalo = d->intervalo / nThreads;

hThreadArray = (HANDLE*) malloc(nThreads * sizeof(HANDLE));
tempMask = d->pMask;

for (i=0; i < nThreads; i++)
{

aux[i].inicio = d->inicio + (i * intervalo);
aux[i].fim = aux[i].inicio + intervalo - 1;
aux[i].vet = d->vet;
aux[i].pMask = (int) pow(2, (float) tempMask);

hThreadArray[i] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&SelectionThreadProc, (LPVOID) &aux[i], 0, &dwThreadId);
SetThreadAffinityMask(hThreadArray[i],aux[i].pMask);

tempMask++;
}

WaitForMultipleObjects(nThreads,hThreadArray,TRUE,INFINITE);
merge(d->vet, d->inicio, d->fim);

for (i=0; i < nThreads; i++)
CloseHandle(hThreadArray[i]);

free(hThreadArray);
return 0;
}

DWORD MainThreadProc (LPVOID lpParam ) //Thread principal
{
int nThreads=2, ThreadNum=0 ,i, tempMask=0;
unsigned int intervalo;

DADOS *d, aux[2];

DWORD dwThreadId;
HANDLE *hThreadArray;

d = (DADOS*) lpParam;
intervalo = N / nThreads;

hThreadArray = (HANDLE*) malloc(nThreads * sizeof(HANDLE));

for (i=0; i < nThreads; i++)
{
ThreadNum = i + 1;
aux[i].fim = ThreadNum * intervalo;
aux[i].inicio = aux[i].fim - intervalo;
aux[i].fim--;
aux[i].vet = d->vet;
aux[i].intervalo = intervalo;
aux[i].pMask = tempMask;

hThreadArray[i] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&MergeThreadProc, (LPVOID) &aux[i], 0, &dwThreadId);
SetThreadAffinityMask(hThreadArray[i],aux[i].pMask);
tempMask+=2;
}

WaitForMultipleObjects(nThreads,hThreadArray,TRUE,INFINITE);
merge(d->vet, d->inicio, d->fim); //Faz a ordenação final, das 2 ultimas listas que variam de 0 até N -1

for (i=0; i < nThreads; i++)
CloseHandle(hThreadArray[i]);
free(hThreadArray);

return 0;
}