En mi estudio de algoritmos de Ordenación en c++ he creado un pequeño archivo unificando todas las funciones y comprobando la eficacia de cada uno utilizando una función de c++ que mide los tiempos de ejecución.
Los métodos utilizados son:
- Método QuickSort
- Método HeapSort
- Método Burbuja
- Método Selección
- Método Inserción
- Método MergeSort
———————————————————————————
#include <stdio.h>
#include <stdlib.h>
#include <iostream>TIEMPOS-EJECUCION-algoritmos-de-ordenacion
#include <vector>
#include <time.h>
using namespace std;
//FUNCIÓN QUE MIDE LOS TIEMPOS DE EJECUCIÓN
timespec diff(timespec start, timespec end){
timespec temp;
if ((end.tv_nsec-start.tv_nsec)<0) {
temp.tv_sec = end.tv_sec-start.tv_sec-1;
temp.tv_nsec = 1000000000+end.tv_nsec-start.tv_nsec;
} else {
temp.tv_sec = end.tv_sec-start.tv_sec;
temp.tv_nsec = end.tv_nsec-start.tv_nsec;
}
return temp;
}
//FUNCIÓN QUE INICIALIZA UN VECTOR DE NÚMEROS ENTEROS
void inicializar (vector <int> & numeros,int cant){
for(int i=0; i < cant; i++ )
numeros.push_back(random()%100);}
//FUNCIÓN QUE MUESTRA EL VECTOR
void mostrar (vector <int> numeros){
cout << “Vector: “<< endl;
for (int i=0;i < numeros.size(); i++)
cout << numeros.at(i) << ” “;
cout << endl;
}
//FUNCIONES MÉTODO ORDENAR MERGESORT
vector <int> ordenarVectores(vector <int> numeros1, vector <int> numeros2){
int i=0,j=0,k=0;
vector <int> numerosTotal;
while (i < numeros1.size() && j < numeros2.size()){
if (numeros1[i] < numeros2[j]){
numerosTotal.push_back(numeros1[i]);
i++;
}
else{
numerosTotal.push_back(numeros2[j]);
j++;
}}
if (i != numeros1.size()){
for (k = i; k < numeros1.size(); k++){
numerosTotal.push_back(numeros1[k]);
}}
else{
for (k = j; k < numeros2.size(); k++){
numerosTotal.push_back(numeros2[k]);
}}
return numerosTotal;
}
vector <int> mergesort (vector <int> numerosTotal){
int k,i,j;
vector <int> numeros1;
vector <int> numeros2;
vector <int> v1;
vector <int> v2;
vector <int> aux;
k = numerosTotal.size()/2;
if (numerosTotal.size() == 1) return numerosTotal;
for (i = 0; i < k; i++ ){
numeros1.push_back(numerosTotal[i]);
}
for (; i < numerosTotal.size(); i++ ){
numeros2.push_back(numerosTotal[i]);
}
v1 = mergesort(numeros1);
v2 = mergesort(numeros2);
aux = ordenarVectores(v1,v2);
return aux;
}
//FUNCIÓN MÉTODO ORDENADAR SELECCIÓN
void ordenarSeleccion(vector <int> & numeros){
int i,j;
int min,aux,pos;
for (i = 0; i < numeros.size(); i++){
min = numeros[i];
for (j = i; j < numeros.size(); j++ ){
if (numeros[j] < min){
min = numeros[j];
pos = j;
}}
aux = numeros[i];
numeros[i] = min;
numeros[pos] = aux;
}}
//FUNCIÓN MÉTODO ORDENADAR BURBUJA
void ordenarBurbuja(vector <int> & numeros){
int i,j;
int aux;
for (j = 0; j < numeros.size(); j++){
for (i = 0; i < numeros.size() – 1; i++){
if (numeros[i] > numeros[i+1]){
aux = numeros[i];
numeros[i] = numeros[i+1];
numeros[i+1] = aux;
}
}}
}
//FUNCIÓN MÉTODO ORDENAR ISNERCION
void ordenarInsercion(vector <int> & numeros){
int i,j;
int aux;
for (i = 0; i < numeros.size(); i++){
j = i;
while ( j > 0 && numeros[j] < numeros[j-1]){
aux = numeros[j-1];
numeros[j-1] = numeros[j];
numeros[j] = aux;
j–;
}}
}
//FUNCIONES MÉTODO ORDENAR HEAPSORT
void heapificar(vector <int> & numeros){
int heapificado,isos,padre;
for (heapificado = 0; heapificado < numeros.size(); heapificado++){
isos = heapificado; // isos = indice sospechoso
while (isos > 0){
padre = (isos-1) / 2;
if (numeros[isos] > numeros[padre]){
//intercambio
int aux;
aux = numeros[isos];
numeros[isos] = numeros[padre];
numeros[padre] = aux;
}
isos = padre;
}}
}
void heapSort(vector <int> & numeros){
int hijoDerecha,hijoIzquierda,isos;
for (int i = numeros.size()-1; i > 0; i–){
//intercambiar
int aux = numeros[0];
int hijoMayor;
numeros[0]=numeros[i];
numeros[i]=aux;
//heapificar
isos = 0;
hijoIzquierda = isos * 2 + 1;
hijoDerecha = isos * 2 + 2;
while(1){
//No tiene hijos
if (hijoIzquierda >= i ) break;
//Solo tiene un hijo
if (hijoDerecha == i && (numeros[isos] < numeros[hijoIzquierda])){
aux = numeros[isos];
numeros[isos] = numeros[hijoIzquierda];
numeros[hijoIzquierda] = aux;
isos = hijoMayor;
hijoIzquierda = isos * 2 + 1;
hijoDerecha = isos * 2 + 2;
break;
}
//Tiene dos hijos
//que hijo es mayor
if ((numeros[isos] < numeros[hijoDerecha]) || (numeros[isos] < numeros[hijoIzquierda])){
//comprobamos que contenido de cada indice es mayor.
if (numeros[hijoIzquierda] > numeros[hijoDerecha]) hijoMayor = hijoIzquierda;
else hijoMayor = hijoDerecha;
}
else break;
// intercambio
aux = numeros[isos];
numeros[isos] = numeros[hijoMayor];
numeros[hijoMayor] = aux;
//isos es ahora el hijo intercambiado
isos = hijoMayor;
hijoIzquierda = isos * 2 + 1;
hijoDerecha = isos * 2 + 2;
}}
}
//FUNCIÓN MÉTODO ORDENAR QUICKSORT
void quickSort(vector <int> & numeros,int ini,int fin){
int iz = ini;//posicio de l’esquerra. Recorre el vector d’esquerra a dreta
int de = fin;//posicio de la dreta. Recorre el vector de dreta a esquerra
int piv = (ini + fin) / 2; //determina la posicio del mig de cada “particio” del vector
int valorPivote = numeros[piv];
int aux;
if (numeros.size() < 2) return;
while ( iz < de ){
//avancem cap a la dreta
while( numeros[iz] < valorPivote)
iz++;
//avancem cap a l’esquerra
while( numeros[de] > valorPivote)
de–;
//intercanviem i avancem els index
if ( iz <= de ){
aux = numeros[de];
numeros[de] = numeros[iz];
numeros[iz] = aux;
iz++;
de–;
}}
if (ini < de)
quickSort(numeros, ini, de);
if (iz < fin)
quickSort(numeros, de+1, fin);
}
//EMPEZAMOS MAIN
int main (int argc, char ** argv){
vector <int> numerosTotal;
vector <int> resultado;
vector <int> numeros;
inicializar(numerosTotal,1000000);
/*ORDENAR HEAPSORT*/
numeros = numerosTotal;
timespec timeh1, timeh2;
int temph;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timeh1);
heapificar(numeros);
heapSort(numeros);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timeh2);
cout<<”Tiempo usado metodo heapSort\n: ” <<diff(timeh1,timeh2).tv_sec<<”:”<<diff(timeh1,timeh2).tv_nsec<<endl;
/*END HEAPSORT*/
/*ORDENAR QUICKSORT*/
numeros = numerosTotal;
timespec timeq1, timeq2;
int tempq;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timeq1);
quickSort(numeros,0,numeros.size()-1);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timeq2);
cout<<”Tiempo usado metodo quickSort\n: ” <<diff(timeq1,timeq2).tv_sec<<”:”<<diff(timeq1,timeq2).tv_nsec<<endl;
/*END QUICKSORT*/
/*INSERCIÓN*/
numeros = numerosTotal;
timespec timei1, timei2;
int tempi;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timei1);
ordenarInsercion(numerosTotal);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timei2);
cout<<”Tiempo usado metodo insercion:\n ” <<diff(timei1,timei2).tv_sec<<”:”<<diff(timei1,timei2).tv_nsec<<endl;
/*END INSERCIÓN*/
/*BURBUJA*/
numeros = numerosTotal;
timespec timeb1, timeb2;
int tempb;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timeb1);
ordenarBurbuja(numeros);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timeb2);
cout<<”Tiempo usado metodo burbuja:\n ” <<diff(timeb1,timeb2).tv_sec<<”:”<<diff(timeb1,timeb2).tv_nsec<<endl;
/*END BURBUJA*/
/*MERGE SORT*/
numeros = numerosTotal;
timespec timem1, timem2;
int tempm;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timem1);
resultado = mergesort(numeros);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timem2);
cout<<”Tiempo usado metodo merge sort\n: ” <<diff(timem1,timem2).tv_sec<<”:”<<diff(timem1,timem2).tv_nsec<<endl;
/*END MERGE SORT*/
/*ORDENAR SELECCION*/
numeros = numerosTotal;
timespec times1, times2;
int temps;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, ×1);
ordenarSeleccion(numeros);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, ×2);
cout<<”Tiempo usado metodo seleccion\n: ” <<diff(times1,times2).tv_sec<<”:”<<diff(times1,times2).tv_nsec<<endl;
/*END ORDENAR SELECCIÓN*/
};
