Reescribí el código del programa utilizado en este artículo un par de veces. Siempre fue interesante cuánto más rápido sería un tipo que otro. Parece que todos los estudiantes las pasan, pero básicamente como una reescritura de un pseudo-algoritmo en una conferencia en un código en algún idioma. Quizás este artículo sea útil para algún programador novato.
Consideremos 5 tipos. Estos son burbuja, agitar, apilar, insertar y rápido.
Para analizar su velocidad, se utilizará la función reloj () antes de ordenar y después de eso, luego se toma su diferencia y averiguamos el tiempo de operación de la clasificación. Usé 100 iteraciones de 1000 valores dados en vectores y una hoja para probar la función integrada sort () de stl. A cada clasificación se le asignan números igualmente dispersos en las matrices en cada iteración. Después de eso, el tiempo se escribe en la variable media de cada clasificación y se divide por el total por el número de iteraciones. Entonces, averiguamos el tiempo de ejecución promedio de cada tipo y eventualmente podemos compararlos en velocidad con los mismos datos iniciales. Los datos se ingresan en matrices usando la función rand ().
Archivo Sorts.h:
#pragma once
#include <iostream>
#include <list>
#include <vector>
#include <iterator>
template <typename T> class Sorts
{
public:
std::list<T> arrayList;
std::vector<T> bubbleArray,insertionArray,heapArray,shakeArray;
float BubbleSort()
{
std::cout <<"Time to Bubble>" << std::endl;
unsigned int start_time = clock(); //
int size = bubbleArray.size();
for (int i = 1; i < size; i++)
for (int j = size-1; j >=i; j--)
if (bubbleArray[j-1] > bubbleArray[j])
swap(&bubbleArray, j - 1, j);
unsigned int end_time = clock(); //
unsigned int search_time = end_time - start_time; //
std::cout << (float)search_time / CLOCKS_PER_SEC << std::endl;
return (float)search_time / CLOCKS_PER_SEC;
}
float InsertionSort()
{
std::cout << "Time to Insertion>" << std::endl;
unsigned int start_time = clock(); //
int size = insertionArray.size();
for (int i = 1; i < size; i++)
{
T tmp = insertionArray[i];
int j = i;
while (j > 0 && insertionArray[j - 1] > tmp)
{
insertionArray[j] = insertionArray[j - 1];
j = j - 1;
}
insertionArray[j] = tmp;
}
unsigned int end_time = clock(); //
unsigned int search_time = end_time - start_time; //
std::cout << (float)search_time / CLOCKS_PER_SEC << std::endl;
return (float)search_time / CLOCKS_PER_SEC;
}
void swap(std::vector<T> *v, int n, int m)
{
T tmp = (*v)[n];
(*v)[n] = (*v)[m];
(*v)[m] = tmp;
}
float HeapSort()
{
std::cout << "Time to Heap>" << std::endl;
unsigned int start_time = clock(); //
int size = heapArray.size();
for (int j = 0; j < size; j++)
{
for (int i = size / 2 - 1 - j / 2; i > -1; i--)
{
if (2 * i + 2 <= size - 1 - j)
{
if (heapArray[2 * i + 1] > heapArray[2 * i + 2])
{
if (heapArray[i] < heapArray[2 * i + 1])
{
swap(&heapArray, i, 2 * i + 1);
}
}
else
if (heapArray[i] < heapArray[2 * i + 2])
{
swap(&heapArray, i, 2 * i + 2);
}
}
else
if (2 * i + 1 <= size - 1 - j)
if (heapArray[i] < heapArray[2 * i + 1])
swap(&heapArray, i, 2 * i + 1);
}
swap(&heapArray, 0, size - 1 - j);
}
unsigned int end_time = clock(); //
unsigned int search_time = end_time - start_time; //
std::cout << (float)search_time / CLOCKS_PER_SEC << std::endl;
return (float)search_time / CLOCKS_PER_SEC;
}
float ShakeSort()
{
std::cout << "Time to Shake>" << std::endl;
unsigned int start_time = clock(); //
int size = shakeArray.size();
int left = 0;
int right = size - 1;
do {
for (int i = left; i < right; i++) {
if (shakeArray[i] > shakeArray[i + 1])
swap(&shakeArray,i,i+1);
}
right--;
for (int i = right; i > left; i--) {
if (shakeArray[i] < shakeArray[i - 1])
swap(&shakeArray, i-1, i);
}
left++;
} while (left < right);
unsigned int end_time = clock(); //
unsigned int search_time = end_time - start_time; //
std::cout << (float)search_time / CLOCKS_PER_SEC << std::endl;
return (float)search_time / CLOCKS_PER_SEC;
}
void PrintArray(int num)
{
switch (num)
{
case 0:
for (typename std::list<T>::iterator it = arrayList.begin(); it != arrayList.end(); it++)
std::cout << (*it) << " ";
break;
case 1:
for (typename std::vector<T>::iterator it = bubbleArray.begin(); it != bubbleArray.end(); it++)
std::cout << (*it) << " ";
break;
case 2:
for (typename std::vector<T>::iterator it = shakeArray.begin(); it != shakeArray.end(); it++)
std::cout << (*it) << " ";
break;
case 3:
for (typename std::vector<T>::iterator it = heapArray.begin(); it != heapArray.end(); it++)
std::cout << (*it) << " ";
break;
case 4:
for (typename std::vector<T>::iterator it = insertionArray.begin(); it != insertionArray.end(); it++)
std::cout << (*it) << " ";
break;
default:
break;
}
std::cout << std::endl;
}
};
Tenga en cuenta que puede utilizar no solo números enteros, sino también números y símbolos reales.
Archivo de programa principal:
#include "Sorts.h"
int main()
{
std::vector<float> vq, vb, vs, vh, vi;
float meanq = 0, meanb = 0, means = 0, meanh = 0, meani = 0;
const int N = 100;
srand(time(0));
for (int i = 0; i < N; i++)
{
std::cout << i+1 << " iteration" << std::endl;
const int iSize = 1000;
auto sort = new Sorts<int>();
for (int i = 0; i < iSize; i++)
{
int num = rand() % iSize;
sort->arrayList.push_back(num);
sort->bubbleArray.push_back(num);
sort->shakeArray.push_back(num);
sort->heapArray.push_back(num);
sort->insertionArray.push_back(num);
}
std::cout << "Time to Quick sort from stl>" << std::endl;
unsigned int start_time = clock(); //
sort->arrayList.sort();
unsigned int end_time = clock(); //
unsigned int search_time = end_time - start_time; //
std::cout << (float)search_time / CLOCKS_PER_SEC << std::endl;
vq.push_back((float)search_time / CLOCKS_PER_SEC);
vb.push_back(sort->BubbleSort());
vs.push_back(sort->ShakeSort());
vh.push_back(sort->HeapSort());
vi.push_back(sort->InsertionSort());
meanq += vq[i];
meanb += vb[i];
means += vs[i];
meanh += vh[i];
meani += vi[i];
//sort->PrintArray(0);
//sort->PrintArray(1);
//sort->PrintArray(2);
//sort->PrintArray(3);
//sort->PrintArray(4);
sort->arrayList.clear();
sort->bubbleArray.clear();
sort->shakeArray.clear();
sort->heapArray.clear();
sort->insertionArray.clear();
std::cout << "end of "<< i + 1 <<" iteration" << std::endl;
}
std::cout << "Results:" << std::endl;
std::cout << "Mean quick=" << (float)meanq / N << std::endl;
std::cout << "Mean bubble=" << (float)meanb / N << std::endl;
std::cout << "Mean shake=" << (float)means / N << std::endl;
std::cout << "Mean heap=" << (float)meanh / N << std::endl;
std::cout << "Mean insertion=" << (float)meani / N << std::endl;
return 0;
}
Cuales son los resultados?
Con un gran margen va ordenando desde stl, luego inserta, piramidal, agitador y termina con una burbuja.
Rápido: 0,00225 ms
Inserción: 0,04482 ms
Montón: 0,07025 ms Agitación
: 0,14186 ms
Burbuja: 0,14324 ms
En principio, las matrices de datos demasiado grandes tardan mucho en clasificarse, pero la clasificación rápida resuelve órdenes de magnitud más rápido que otras.