QuickVSInsertion Sorting C Program

QuickVSInsertion Sorting C Program

How to write a C Program to QuickVSInsertion Sorting C Programming Language ? 


Solution:
#include <stdio.h>
#include <stdlib.h> //usado para a fx system("cls"); que limpa a tela
#include <windows.h>
#include <conio.h> //no caso se eu precisar de pausar a tela



typedef long tipoChave;

typedef struct TipoItem {
tipoChave chave;             //Cria uma variavel long que sera a chave
}TipoItem;

void Quicksort(TipoItem* A, int esq, int dir){       //define a função principal do quicksort, que sera chamado recursivamente
     int pivoPos;                                    //cria a variavel que sera o pivo
     if (esq < dir){                          //Condição de parada
         pivoPos = Particao(A, esq, dir);     //Cria 2 partições e insere pivô na posição correta
         Quicksort(A, esq, pivoPos - 1);      //1ª partição
         Quicksort(A, pivoPos + 1, dir);      //2ª partição
     }
}

int Particao(TipoItem* A, int esq, int dir){
    int i, j;                          //cria uma variavel simples que sera usada como contador
    tipoChave pivo;                    //cria uma variavel para o pivo
    TipoItem temp;                     //cria uma variavel temporaria
    pivo = A[dir].chave;               //Aponta para o último elemento
    i = esq - 1;                       //2ª partição está vazia
    for (j = esq; j < dir; j++) {      //Percorre o pedaço inteiro
        if (A[j].chave <= pivo){       //verifica se e da 1ª partição
           i++;                         //incrementa o i que estava na posicao -1
           temp = A[i];                 //movimentaçao de dados
           A[i] = A[j];                 //movimentaçao de dados
           A[j] = temp;                 //movimentaçao de dados
        }
    }
    temp = A[i+1];                        //Troca o pivô com o  1 da 2 partição
    A[i+1] = A[dir];                        //movimentacao de dados
    A[dir] = temp;                          //movimentacao de dados
    return i + 1;                         //Retorna a posição do pivô
}

void ordenaCase1(TipoItem* arquivoUm){
    int i, inicio, final;
    int tmili;
    unsigned long long int comp, mover;
    FILE *arq;

    arq = fopen("Vetor-6000-Aleatorio.txt","r");            //abre o arquivo txt que vai ser ordenado

    printf("Iniciando QuickSort\n\nAguarde a ordenacao...\n\n");    //feedback para o usuario

    // Carrega o arquivo para a memória
    for (i = 1; i <= 6000; i++){
        fscanf(arq, "%d", &arquivoUm[i-1].chave);
    }
    inicio = GetTickCount();           //captura o tempo em que a ordenaçao comeca

    Quicksort(arquivoUm, 0, 5999);     //Chama a funçao do QuickSort

    final = GetTickCount();            //captura o tempo final, depois de tudo esta ordenado

    tmili = final - inicio; //efetua a conversao para o tempo ser exibido em segundos

    printf("Tempo decorrido em mili-segundos: %d\n\n", tmili); //utilizando o tempo em milisegundo, pois e muito rapido

    arq = fopen("Vetor-6000-Aleatorio-Saida.txt","w");      //cria o arquivo ordenado em txt

    for(i = 0; i < 6000; i++){
        fprintf(arq, "%d\n", arquivoUm[i].chave);           //insere os elementos ordenados no arquivo criado anteriormente
    }
    fflush(arq);            //limpa da memoria o arquivo
    fclose(arq);            //fecha o arquivo txt
}

void ordenaCase2(TipoItem* arquivoUm){
    int i, inicio, final;
    int tmili;
    unsigned long long int comp, mover;
    FILE *arq;

    arq = fopen("Vetor-6000-Crescente.txt","r");            //abre o arquivo txt que vai ser ordenado

    printf("Iniciando QuickSort\n\nAguarde a ordenacao...\n\n");    //feedback para o usuario

    // Carrega o arquivo para a memória
    for (i = 1; i <= 6000; i++){
        fscanf(arq, "%d", &arquivoUm[i-1].chave);
    }
    inicio = GetTickCount();           //captura o tempo em que a ordenaçao comeca

    Quicksort(arquivoUm, 0, 5999);     //Chama a funçao do QuickSort

    final = GetTickCount();            //captura o tempo final, depois de tudo esta ordenado

    tmili = final - inicio; //efetua a conversao para o tempo ser exibido em segundos

    printf("Tempo decorrido em mili-segundos: %d\n\n", tmili); //utilizando o tempo em milisegundo, pois e muito rapido

    arq = fopen("Vetor-6000-Crescente-Saida.txt","w");      //cria o arquivo ordenado em txt

    for(i = 0; i < 6000; i++){
        fprintf(arq, "%d\n", arquivoUm[i].chave);           //insere os elementos ordenados no arquivo criado anteriormente
    }
    fflush(arq);            //limpa da memoria o arquivo
    fclose(arq);            //fecha o arquivo txt
}

void ordenaCase3(TipoItem* arquivoUm){
    int i, inicio, final;
    int tmili;
    unsigned long long int comp, mover;
    FILE *arq;

    arq = fopen("Vetor-6000-Decrescente.txt","r");            //abre o arquivo txt que vai ser ordenado

    printf("Iniciando QuickSort\n\nAguarde a ordenacao...\n\n");    //feedback para o usuario

    // Carrega o arquivo para a memória
    for (i = 1; i <= 6000; i++){
        fscanf(arq, "%d", &arquivoUm[i-1].chave);
    }
    inicio = GetTickCount();           //captura o tempo em que a ordenaçao comeca

    Quicksort(arquivoUm, 0, 5999);     //Chama a funçao do QuickSort

    final = GetTickCount();            //captura o tempo final, depois de tudo esta ordenado

    tmili = final - inicio; //efetua a conversao para o tempo ser exibido em segundos

    printf("Tempo decorrido em mili-segundos: %d\n\n", tmili); //utilizando o tempo em milisegundo, pois e muito rapido

    arq = fopen("Vetor-6000-Decrescente-Saida.txt","w");      //cria o arquivo ordenado em txt

    for(i = 0; i < 6000; i++){
        fprintf(arq, "%d\n", arquivoUm[i].chave);           //insere os elementos ordenados no arquivo criado anteriormente
    }
    fflush(arq);            //limpa da memoria o arquivo
    fclose(arq);            //fecha o arquivo txt
}

void ordenaCase4(TipoItem* arquivoDois){
    int i, inicio, final;
    float tmili;
    unsigned long long int comp, mover;
    float tEmSegundos;
    FILE *arq;

    arq = fopen("Vetor-60000-Aleatorio.txt","r");            //abre o arquivo txt que vai ser ordenado

    printf("Iniciando QuickSort\n\nAguarde a ordenacao...\n\n");    //feedback para o usuario

    // Carrega o arquivo para a memória
    for (i = 1; i <= 60000; i++){
        fscanf(arq, "%d", &arquivoDois[i-1].chave);
    }
    inicio = GetTickCount();           //captura o tempo em que a ordenaçao comeca

    Quicksort(arquivoDois, 0, 59999);     //Chama a funçao do QuickSort

    final = GetTickCount();            //captura o tempo final, depois de tudo esta ordenado

    tmili = (final - inicio) / 1



Learn More :

Sort

Learn More Multiple Choice Question :