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