Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Comparação tempos ordenação BubbleSort, Seleção, Inserção, MergeSort e QuickSort
// Criado por: profa. Divani Barbosa Gavinier
// Currículo Lattes: http://lattes.cnpq.br/8503400830635447
// divanibarbosa@gmail.com
/* Crie um código em linguagem C++ que compare o tempo gasto pelo computador para ordenar um vetor de tamanho lido pelo usuário.
Use os métodos simples visto em aula e considere:
Atribuição de valores aleatórios entre zero e quinhentos ao vetor.
Crie um cópia do vetor gerado aleatoriamente e ordene a cópia.
Depois de ordenar a cópia, atribua os valores do vetor original a mesma, para que possa ordenar novamente através de outro método de ordenação e a comparação seja eficaz.
*/
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
/* ****************************************** */
void imprime(int *, int);
void bubblesort(int *, int);
void selecao(int *, int);
void insercao(int *, int);
void intercala(int *, int, int, int);
void MergeSort (int *, int, int);
void QuickSort (int *, int, int);
/* ****************************************** */
main() {
clock_t inicio;
int n, i;
float tempo;
cout << "Entre com a quantidade de elementos que deseja ordenar: ";
cin >> n;
int v[n];
int copia[n];
srand(time(NULL));
for (i=0; i<n; i++) v[i] = rand()%501;
/* cout << "v = "; imprime(v,n); */
for(i=0; i<n; i++) copia[i] = v[i]; /* vetor copia recebe conteudo do vetor v */
inicio = clock();
bubblesort(copia,n);
tempo = (float)(clock() - inicio)/CLOCKS_PER_SEC;
cout << "Tempo Gasto BubbleSort: " << tempo << " segundos\n";
for(i=0; i<n; i++) copia[i] = v[i];
inicio = clock();
selecao(copia,n);
tempo = (float)(clock() - inicio)/CLOCKS_PER_SEC;
cout << "Tempo Gasto Selecao: " << tempo << " segundos\n";
for(i=0; i<n; i++) copia[i] = v[i];
inicio = clock();
insercao(copia,n);
tempo = (float)(clock() - inicio)/CLOCKS_PER_SEC;
cout << "Tempo Gasto Insercao: " << tempo << " segundos\n";
for(i=0; i<n; i++) copia[i] = v[i];
inicio = clock();
MergeSort(copia,0,n-1);
tempo = (float)(clock() - inicio)/CLOCKS_PER_SEC;
cout << "Tempo Gasto MergeSort: " << tempo << " segundos\n";
for(i=0; i<n; i++) copia[i] = v[i];
inicio = clock();
QuickSort(copia,0,n-1);
tempo = (float)(clock() - inicio)/CLOCKS_PER_SEC;
cout << "Tempo Gasto QuickSort: " << tempo << " segundos\n";
}
/* ****************************************** */
void imprime(int *v, int n) {
for (int i=0; i<n; i++) cout << v[i] << " ";
cout << endl;
}
/* ****************************************** */
void bubblesort(int *v, int n) {
for(int i=0; i<n; i++)
for(int j=0; j < n-1; j++)
if (v[j] > v[j+1]) {
int temp = v[j];
v[j] = v[j+1];
v[j+1] = temp;
}
}
/* ****************************************** */
void selecao(int *v, int n) {
int min;
for (int i=0; i<(n-1); i++) {
min=i;
for (int j=i+1; j<n; j++) {
if (v[j] < v[min]) min = j;
}
int temp = v[i];
v[i] = v[min];
v[min] = temp;
}
}
/* ****************************************** */
void insercao(int *v, int n) {
int i, j;
int temp;
for (i=1; i<n; i++) {
temp = v[i];
j = i;
while ((j>0) && (v[j-1]>temp)) {
v[j] = v[j-1];
j = j - 1;
}
v[j] = temp;
}
}
/* ****************************************** */
void MergeSort (int *v, int inicio, int fim) {
if(inicio==fim) return;
int meio=(inicio+fim)/2;
MergeSort(v,inicio,meio);
MergeSort(v,meio+1,fim);
intercala(v,inicio,meio,fim);
}
/* ****************************************** */
void intercala(int *v, int inicio, int meio, int fim) {
int aux[fim-inicio+1];
int i = inicio;
int j = meio+1;
int k = 0;
while ( i<=meio && j<=fim )
if ( v[i] <= v[j] ) aux[k++] = v[i++];
else aux[k++] = v[j++];
while ( i <= meio ) aux[k++] = v[i++];
while ( j <= fim ) aux[k++] = v[j++];
for ( i=0; i<(fim-inicio+1); i++) v[inicio + i] = aux[i];
}
/* ****************************************** */
void QuickSort (int *v, int esq, int dir) {
int i = esq;
int j = dir;
int pivo = v [ (esq+dir)/2 ];
int aux;
do {
while (v[i]<pivo && i<dir) i++;
while (pivo<v[j] && j>esq) j--;
if (i<=j) {
aux = v[i];
v[i] = v[j];
v[j] = aux;
i++;
j--;
}
} while (i <= j);
if (esq < j) QuickSort(v,esq,j);
if (i < dir) QuickSort(v,i,dir);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment