Exe03 - Quick Sort implementação própria com tempos de trocas

[waldeyr]

Deixe aqui seu nome e código no comentário.

[4ven]

// Samuel Sergio Garcia Espinosa

#include<stdlib.h> 
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define TAMANHO 100000

long qComp, qTrocas;

void mostrarDados(long comp, long trocas, long tempo)
{
    printf("Quantidade de comparaçoes: %ld \n", comp);
    printf("Quantidade de trocas: %ld \n", trocas);
    printf("Tempo gasto: %ld", tempo);
    printf("\n");
}

void Quick(int vetor[TAMANHO], int inicio, int fim)
{
    int pivo, aux, i, j, meio;

    i = inicio;
    j = fim;

    meio = (int) ((i + j) / 2);
    pivo = vetor[meio];

    do
    {
        while (vetor[i] < pivo)
        {
            i = i + 1;
            qComp++;
        }

        while (vetor[j] > pivo)
        {
            j = j - 1;
            qComp++;
        }   
        if(i<=j)
        {
            aux = vetor[i];
            vetor[i] = vetor[j];
            vetor[j] = aux;
            i = i + 1;
            j = j - 1;
            qTrocas++;
        }
    }
    while(j > i);

    if(inicio < j) Quick(vetor, inicio, j);
    if(i < fim) Quick(vetor, i, fim);   
}

void main()
{
    long tempoR, tempoC, tempoD;
    int vetorR[TAMANHO], vetorC[TAMANHO], vetorD[TAMANHO]; //vetor com tamanho definido
    clock_t tempoInicial, tempoFinal; //Variaveis para guardar o tempo de execucao
    srand(time(NULL)); //Cria uma semente para numeros aleatorios

    // VALORES RANDOMICOS
    tempoInicial = clock(); //inicia contagem do tempo
    for (int i = 0; i < TAMANHO; i++)
        vetorR[i] = rand() % 10; //Atribui um inteiro aleatorio entre 0 e 9

    //Chama a fucao passando o vetor como parametro
    Quick(vetorR, 0, TAMANHO-1);
    printf("\n");

    tempoFinal = clock(); //finaliza contagem do tempo
    tempoR = tempoFinal - tempoInicial;

    //calcula e mostra o tempo total de execucao
    printf("Valores Randomicos \n");
    mostrarDados(qComp, qTrocas, tempoR);

    // VALORES CRESCENTES
    qComp = 0;
    qTrocas = 0;
    tempoInicial = clock(); //inicia contagem do tempo

    for (int i = 0; i < TAMANHO; i++)
        vetorC[i] = i+1; 

    //Chama a fucao passando o vetor como parametro
    Quick(vetorC, 0, TAMANHO-1);
    printf("\n");

    tempoFinal = clock(); //finaliza contagem do tempo
    tempoC = tempoFinal - tempoInicial;

    //calcula e mostra o tempo total de execucao
    printf("Valores Crescentes \n");
    mostrarDados(qComp, qTrocas, tempoC);

    // VALORES DECRESCENTES
    qComp = 0;
    qTrocas = 0;
    long count = TAMANHO;
    tempoInicial = clock(); //inicia contagem do tempo
    for (int i = 0; i < TAMANHO; i++)
    {
        vetorD[i] = count; 
        count--;
    }

    //Chama a fucao passando o vetor como parametro
    Quick(vetorD, 0, TAMANHO-1);
    printf("\n");

    tempoFinal = clock(); //finaliza contagem do tempo
    tempoD = tempoFinal - tempoInicial;

    //calcula e mostra o tempo total de execucao
    printf("Valores Decrescentes \n");
    mostrarDados(qComp, qTrocas, tempoD);
}

[LarissaJacobina]

Larissa S. Jacobina

#include<stdlib.h> 
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define TAMANHO 100000
void Quick(int vetor[TAMANHO], int inicio, int fim);

int comp = 0, troca = 0;

int aleatorio() {

    int vetor[TAMANHO]; //vetor com tamanho definido
    clock_t tempoInicial, tempoFinal; //Variaveis para guardar o tempo de execucao
    srand(time(NULL)); //Cria uma semente para numeros aleatorios
    tempoInicial = clock(); //inicia contagem do tempo
    for (int i = 0; i < TAMANHO; i++) {
        vetor[i] = rand() % 10; //Atribui um inteiro aleatorio entre 0 e 9
    }
    //Mostra valores do vetor nao ordenado
    for (int i = 0; i < TAMANHO; i++) {
        printf("%d\t", vetor[i]);
    }
    printf("\n");
    //Chama a fucao passando o vetor como parametro
    Quick(vetor, 0, TAMANHO - 1);

    //Mostra valores do vetor ordenado
   for (int i = 0; i < TAMANHO; i++) {
       printf("%d\t", vetor[i]);
    } 
    printf("\nComparação: %d", comp);
    printf("\nTroca: %d", troca);
    printf("\n");
    tempoFinal = clock(); //finaliza contagem do tempo
    //calcula e mostra o tempo total de execucao
    printf("Tempo: %f s\n", (double) (tempoFinal - tempoInicial) / CLOCKS_PER_SEC);
}

int crescente() {

    int vetor[TAMANHO]; //vetor com tamanho definido
    clock_t tempoInicial, tempoFinal; //Variaveis para guardar o tempo de execucao
    //srand(time(NULL)); //Cria uma semente para numeros aleatorios
    tempoInicial = clock(); //inicia contagem do tempo
    for (int i = 0; i < TAMANHO; i++) {
        vetor[i] = i; //Atribui um inteiro aleatorio entre 0 e 9
    }
    //Mostra valores do vetor nao ordenado
    for (int i = 0; i < TAMANHO; i++) {
        printf("%d\t", vetor[i]);
    }
    printf("\n");
    //Chama a fucao passando o vetor como parametro
    Quick(vetor, 0, TAMANHO - 1);

    //Mostra valores do vetor ordenado
   for (int i = 0; i < TAMANHO; i++) {
       printf("%d\t", vetor[i]);
    } 
    printf("\nComparação: %d", comp);
    printf("\nTroca: %d", troca);
    printf("\n");
    tempoFinal = clock(); //finaliza contagem do tempo
    //calcula e mostra o tempo total de execucao
    printf("Tempo: %f s\n", (double) (tempoFinal - tempoInicial) / CLOCKS_PER_SEC);
}

int decrescente() {

    int vetor[TAMANHO]; //vetor com tamanho definido
    clock_t tempoInicial, tempoFinal; //Variaveis para guardar o tempo de execucao
    //srand(time(NULL)); //Cria uma semente para numeros aleatorios
    tempoInicial = clock(); //inicia contagem do tempo
    for (int i = 0; i < TAMANHO; i++) {
        vetor[i] = TAMANHO - i; //Atribui um inteiro aleatorio entre 0 e 9
    }
    //Mostra valores do vetor nao ordenado
    for (int i = 0; i < TAMANHO; i++) {
        printf("%d\t", vetor[i]);
    }
    printf("\n");
    //Chama a fucao passando o vetor como parametro
    Quick(vetor, 0, TAMANHO - 1);

    //Mostra valores do vetor ordenado
   for (int i = 0; i < TAMANHO; i++) {
       printf("%d\t", vetor[i]);
    } 
    printf("\nComparação: %d", comp);
    printf("\nTroca: %d", troca);
    printf("\n");
    tempoFinal = clock(); //finaliza contagem do tempo
    //calcula e mostra o tempo total de execucao
    printf("Tempo: %f s\n", (double) (tempoFinal - tempoInicial) / CLOCKS_PER_SEC);
}

void Quick(int vetor[TAMANHO], int inicio, int fim){

   int pivo, aux, i, j, meio;

   i = inicio;
   j = fim;

   meio = (int) ((i + j) / 2);
   pivo = vetor[meio];

   do{
      while (vetor[i] < pivo) i = i + 1;
      while (vetor[j] > pivo) j = j - 1;

      if(i <= j){
         aux = vetor[i];
         vetor[i] = vetor[j];
         vetor[j] = aux;
         i = i + 1;
         j = j - 1;
         troca = troca + 1;
      }
      comp = comp + 1;
   }while(j > i);

   if(inicio < j) Quick(vetor, inicio, j);
   if(i < fim) Quick(vetor, i, fim);

}

void main() {

    int opcao = 0;
    printf("Aleatório = 1\n Crescente = 2\n Decrescente = 3\n");
    printf("Ordem: ");
    scanf("%d", &opcao);
    printf("\n");

    switch (opcao) {
    case 1:
    aleatorio();
    break;

    case 2:
    crescente();
    break;

    case 3:
    decrescente();
    break;
    }
}

[Vanderson11]

Vanderson leite campos

include

include

include

include

define TAMANHO 100000

void quick_sort(int *a, int l, int r); int compar=0,troca=0;

int aleatorio(){

 int vetor[TAMANHO]; 
 clock_t tempoInicial, tempoFinal; 
 srand(time(NULL)); 
 tempoInicial = clock(); 

 for (int i = 0; i < TAMANHO; i++) {
     vetor[i] = rand() % 10; 
 }

 for (int i = 0; i < TAMANHO; i++) {
     printf("%d\t", vetor[i]);
 }
 printf("\n");

 quick_sort(vetor, 0, TAMANHO - 1);    

 for (int i = 0; i < TAMANHO; i++) {
     printf("%d\t", vetor[i]);
 }
 printf("\n");

 printf("As trocas:%d\n",troca);
 printf("As comparacoes:%d\n",compar);

 tempoFinal = clock(); 

 printf("Tempo: %f s\n", (double) (tempoFinal - tempoInicial) / CLOCKS_PER_SEC);    

 }

int crescente(){

 int vetor[TAMANHO]; 
 clock_t tempoInicial, tempoFinal; 
 srand(time(NULL)); 
 tempoInicial = clock(); 

 for (int i = 0; i < TAMANHO; i++) {
     vetor[i] = i; 
 }

 for (int i = 0; i < TAMANHO; i++) {
     printf("%d\t", vetor[i]);
 }
 printf("\n");

 quick_sort(vetor, 0, TAMANHO - 1);    

 for (int i = 0; i < TAMANHO; i++) {
     printf("%d\t", vetor[i]);
 }
 printf("\n");

 printf("As trocas:%d\n",troca);
 printf("As comparacoes:%d\n",compar);

 tempoFinal = clock(); 

 printf("Tempo: %f s\n", (double) (tempoFinal - tempoInicial) / CLOCKS_PER_SEC);        

 }

int decrescente(){

 int vetor[TAMANHO]; 
 clock_t tempoInicial, tempoFinal; 
 srand(time(NULL)); 
 tempoInicial = clock(); 

 for (int i = 0; i < TAMANHO; i++) {
     vetor[i] =TAMANHO-i; 
 }

 for (int i = 0; i < TAMANHO; i++) {
     printf("%d\t", vetor[i]);
 }
 printf("\n");

 quick_sort(vetor, 0, TAMANHO - 1);    

 for (int i = 0; i < TAMANHO; i++) {
     printf("%d\t", vetor[i]);
 }
 printf("\n");

 printf("As trocas:%d\n",troca);
 printf("As comparacoes:%d\n",compar);

 tempoFinal = clock(); 

 printf("Tempo: %f s\n", (double) (tempoFinal - tempoInicial) / CLOCKS_PER_SEC);     
}     

void main() {

int x;
printf("1 - Aleatorio\n");
printf("2 - Crescente\n");
printf("3 - Decrescente\n");
printf("Escolha uma opcao:");
scanf("%d",&x);
printf("\n");

switch(x){
        case 1:
               aleatorio(); 
             break;

        case 2:
               crescente();
             break;
        case 3:
               decrescente();             
             break;  

} 

}

void quick_sort(int *a, int l, int r) {

int i, j, x, y;

i = l;
j = r;
x = a[(l + r) / 2];

while(i <= j) {
    while(a[i] < x && i < r) {
        i++;
        compar++;
    }
    while(a[j] > x && j > l) {
        j--;
        compar++;
    }
    if(i <= j) {
        y = a[i];
        a[i] = a[j];
        a[j] = y;
        i++;
        j--;
        troca++;

    }
}

if(j > l) {
    quick_sort(a, l, j);
}
if(i < r) {
    quick_sort(a, i, r);

}

}

[Samuel-Amaro]

/Aluno: Samuel Amaro/

include

include

include

include

include

define TAMANHO 100000

//função que prenche vetor das maneiras pedidas void prenche(int vetor[],int tamanho,char tipo); // variaveis globais void quickSort(int V, int inicio, int fim); int particiona(int V, int inicio, int final); static long troca = 0; static long compara = 0; void main() { int vetor[TAMANHO]; clock_t Inicia_tempo, fecha_tempo; Inicia_tempo = clock(); //prenchendo meu vetor c - crescente/d - decrescente/a - aleatorio prenche(vetor,TAMANHO,'d'); quickSort(vetor,0,TAMANHO - 1); for(int i = 0; i < TAMANHO; i += 1) { printf("%d ",vetor[i]); } printf("\n\n"); fecha_tempo = clock(); printf("tempo gasto na execução: %f\n", (double) (fecha_tempo - Inicia_tempo) / CLOCKS_PER_SEC); printf("Qtd de trocas %d e compara %d\n",troca,compara); }

/função que preenche vetor/ void prenche(int vetor[],int tamanho,char tipo) { int cont_cresce = 0, cont_decres = 100000; if(tipo == 'c') { //zera_vet(vetor,TAMANHO); printf("Valores não Ordenados\n"); for(int i = 0; i < TAMANHO; i += 1) { vetor[i] = cont_cresce += 1; printf("%d \t",vetor[i]); } printf("\n\n"); } if(tipo == 'd') { printf("Valores não Ordenados \n"); //zera_vet(vetor,TAMANHO); for(int i = 0; i < TAMANHO; i += 1) { vetor[i] = cont_decres -= 1; printf("%d \t",vetor[i]); } printf("\n\n"); } srand( time( NULL )); if(tipo == 'a') { printf("Valores não Ordenados \n"); //zera_vet(vetor,TAMANHO); for(int i = 0; i < TAMANHO; i += 1) { vetor[i] = rand() % 100000 + 1; printf("%d \t",vetor[i]); } printf("\n\n"); } }

/função que chama pivo e a cada recursiva vai trocando o pivor/ void quickSort(int V, int inicio, int fim) { int pivo; if(fim > inicio){ pivo = particiona(V, inicio, fim); quickSort(V, inicio, pivo-1); quickSort(V, pivo+1, fim); } } /função que fas trocas e verificações baseadas no pivo/ int particiona(int V, int inicio, int final ){ int esq, dir, pivo, aux; esq = inicio; dir = final; pivo = V[inicio]; while(esq < dir){ //compara += 1; while(V[esq] <= pivo) { esq++; compara += 1;

    }
    while(V[dir] > pivo) {
        dir--;
        compara += 1;
        //troca -= 1;
    }
    if(esq < dir){
        troca += 1;
        aux = V[esq];
        V[esq] = V[dir];
        V[dir] = aux;
    }
    compara += 1;
    //if(V[esq] >= pivo){
    //troca -= 1;
    //}

}

V[inicio] = V[dir];
V[dir] = pivo;
troca += 1;
return dir;

}

``

[gearle01]

include

include

include

include

define TAMANHO 100000

void quick_sort(int *a, int l, int r); int compas=0,troca=0;

//——————————————————aleatório———————————— int aleatorio(){

int vetor[TAMANHO]; clock_t tempoInicial, tempoFinal; srand(time(NULL)); tempoInicial = clock();

for (int i = 0; i < TAMANHO; i++) { vetor[i] = rand() % 10; }

for (int i = 0; i < TAMANHO; i++) { printf("%d\t", vetor[i]); } printf("\n");

quick_sort(vetor, 0, TAMANHO - 1);

for (int i = 0; i < TAMANHO; i++) { printf("%d\t", vetor[i]); } printf("\n");

printf("As trocas:%d\n",troca); printf("As comparacoes:%d\n",compas);

tempoFinal = clock();

printf("Tempo: %f s\n", (double) (tempoFinal - tempoInicial) / CLOCKS_PER_SEC);

} //——————————————crescente———————————————— int crescente(){

int vetor[TAMANHO]; clock_t tempoInicial, tempoFinal; srand(time(NULL)); tempoInicial = clock();

for (int i = 0; i < TAMANHO; i++) { vetor[i] = i; }

for (int i = 0; i < TAMANHO; i++) { printf("%d\t", vetor[i]); } printf("\n");

quick_sort(vetor, 0, TAMANHO - 1);

for (int i = 0; i < TAMANHO; i++) { printf("%d\t", vetor[i]); } printf("\n");

printf("As trocas:%d\n",troca); printf("As comparacoes:%d\n",compas);

tempoFinal = clock();

printf("Tempo: %f s\n", (double) (tempoFinal - tempoInicial) / CLOCKS_PER_SEC);

} //—————————————-decrescente————————- int decrescente(){

int vetor[TAMANHO]; clock_t tempoInicial, tempoFinal; srand(time(NULL)); tempoInicial = clock();

for (int i = 0; i < TAMANHO; i++) { vetor[i] =TAMANHO-i; }

for (int i = 0; i < TAMANHO; i++) { printf("%d\t", vetor[i]); } printf("\n");

quick_sort(vetor, 0, TAMANHO - 1);

for (int i = 0; i < TAMANHO; i++) { printf("%d\t", vetor[i]); } printf("\n");

printf("As trocas:%d\n",troca); printf("As comparacoes:%d\n",compas);

tempoFinal = clock();

printf("Tempo: %f s\n", (double) (tempoFinal - tempoInicial) / CLOCKS_PER_SEC);
}
void main() {

int x; printf("1 - Aleatorio\n"); printf("2 - Crescente\n"); printf("3 - Decrescente\n"); printf("Escolha uma opcão\n"); scanf("%d",&x); printf("\n");

switch(x){ case 1: aleatorio(); break;

    case 2:
           crescente();
         break;
    case 3:
           decrescente();             
         break;

} } void quick_sort(int *a, int l, int r) {

int i, j, x, y;

i = l; j = r; x = a[(l + r) / 2];

while(i <= j) { while(a[i] < x && i < r) { i++; compas++; } while(a[j] > x && j > l) { j--; compas++; } if(i <= j) { y = a[i]; a[i] = a[j]; a[j] = y; i++; j--; troca++; } } if(j > l) { quick_sort(a, l, j); } if(i < r) { quick_sort(a, i, r); } }

[Judy-Ellen]

\JUDY ELLEN VERA MARTINS 20171070130234

include

include

include

include

define TAMANHO 100000

void Quick(int vetor[TAMANHO], int inicio, int fim);

int comp = 0, troca = 0;

int aleatorio() {

int vetor[TAMANHO]; 
clock_t tempoInicial, tempoFinal; //Variaveis para guardar o tempo de execucao
srand(time(NULL)); //Cria uma semente para numeros aleatorios
tempoInicial = clock(); //inicia contagem do tempo
for (int i = 0; i < TAMANHO; i++) {
    vetor[i] = rand() % 10; //Atribui um numero aleatorio entre 0 e 9
}
//Mostra valores do vetor nao ordenado
for (int i = 0; i < TAMANHO; i++) {
    printf("%d\t", vetor[i]);
}
printf("\n");
//Chama a fucao passando o vetor como parametro
Quick(vetor, 0, TAMANHO - 1);

//Mostra valores do vetor ordenado
for (int i = 0; i < TAMANHO; i++) {
    printf("%d\t", vetor[i]);
}
printf("\nComparação: %d", comp);
printf("\nTroca: %d", troca);
printf("\n");
tempoFinal = clock(); //finaliza contagem do tempo
printf("Tempo: %f s\n", (double) (tempoFinal - tempoInicial) / CLOCKS_PER_SEC);

}

int cres() {

int vetor[TAMANHO]; //vetor com tamanho definido
clock_t TI, TF; //Variaveis para guardar o tempo de execucao
//srand(time(NULL)); //Cria uma semente para numeros aleatorios
TI = clock(); //inicia contagem do tempo
for (int i = 0; i < TAMANHO; i++) {
    vetor[i] = i; //Atribui um inteiro aleatorio entre 0 e 9
}
//Mostra valores do vetor nao ordenado
for (int i = 0; i < TAMANHO; i++) {
    printf("%d\t", vetor[i]);
}
printf("\n");
//Chama a fucao passando o vetor como parametro
Quick(vetor, 0, TAMANHO - 1);

//Mostra valores do vetor ordenado
for (int i = 0; i < TAMANHO; i++) {
    printf("%d\t", vetor[i]);
}
printf("\nComparação: %d", comp);
printf("\nTroca: %d", troca);
printf("\n");
TF = clock(); //finaliza contagem do tempo
//calcula e mostra o tempo total de execucao
printf("Tempo: %f s\n", (double) (TF - TI) / CLOCKS_PER_SEC);

}

int dec() {

int vetor[TAMANHO]; //vetor com tamanho definido
clock_t tempoInicial, tempoFinal; //Variaveis para guardar o tempo de execucao
//srand(time(NULL)); //Cria uma semente para numeros aleatorios
tempoInicial = clock(); //inicia contagem do tempo
for (int i = 0; i < TAMANHO; i++) {
    vetor[i] = TAMANHO - i; //Atribui um inteiro aleatorio entre 0 e 9
}
//Mostra valores do vetor nao ordenado
for (int i = 0; i < TAMANHO; i++) {
    printf("%d\t", vetor[i]);
}
printf("\n");
//Chama a fucao passando o vetor como parametro
Quick(vetor, 0, TAMANHO - 1);

//Mostra valores do vetor ordenado
for (int i = 0; i < TAMANHO; i++) {
    printf("%d\t", vetor[i]);
}
printf("\nComparação: %d", comp);
printf("\nTroca: %d", troca);
printf("\n");
tempoFinal = clock(); //finaliza contagem do tempo
//calcula e mostra o tempo total de execucao
printf("Tempo: %f s\n", (double) (tempoFinal - tempoInicial) / CLOCKS_PER_SEC);

}

void Quick(int vetor[TAMANHO], int inicio, int fim) {

int fixo, aux, i, j, meio;

i = inicio;
j = fim;

meio = (int) ((i + j) / 2);
fixo = vetor[meio];

do {
    while (vetor[i] < fixo) i = i + 1;
    while (vetor[j] > fixo) j = j - 1;

    if (i <= j) {
        aux = vetor[i];
        vetor[i] = vetor[j];
        vetor[j] = aux;
        i = i + 1;
        j = j - 1;
        troca = troca + 1;
    }
    comp = comp + 1;
} while (j > i);

if (inicio < j) Quick(vetor, inicio, j);
if (i < fim) Quick(vetor, i, fim);

}

void main() {

int opcao = 0;
printf("Aleatório = 1\t Crescente = 2\t Decrescente = 3\t");
printf("Ordem: ");
scanf("%d", &opcao);
printf("\n");

switch (opcao) {
    case 1:
        aleatorio();
        break;

    case 2:
        cres();
        break;

    case 3:
        dec();
        break;
}

}