J'ai réécrit le code du programme utilisé dans cet article plusieurs fois. Il était toujours intéressant de voir à quel point un type serait beaucoup plus rapide qu'un autre. Ils semblent être passés par tous les étudiants, mais essentiellement comme une réécriture d'un pseudo-algorithme dans une conférence en un code dans une langue. Peut-être que cet article sera utile pour certains programmeurs novices.
Considérons 5 sortes. Ce sont des bulles, des secousses, des tas, des insertions et des rapides.
Pour analyser leur vitesse, la fonction clock () sera utilisée avant le tri et après cela, puis leur différence est prise et nous découvrons le temps de fonctionnement du tri. J'ai utilisé 100 itérations de 1000 valeurs données dans des vecteurs et une feuille pour tester la fonction intégrée sort () de stl. Chaque tri reçoit des nombres également répartis sur les tableaux à chaque itération. Après cela, le temps est écrit dans la variable moyenne de chaque sorte et divisé par le total par le nombre d'itérations. Nous découvrons donc le temps de fonctionnement moyen de chaque tri et nous pouvons éventuellement les comparer en vitesse avec les mêmes données initiales. Les données sont entrées dans des tableaux à l'aide de la fonction rand ().
Fichier 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;
}
};
Notez que vous pouvez utiliser non seulement des entiers, mais également des nombres réels et des symboles.
Fichier programme 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;
}
Quels sont les résultats?
Avec une grande marge va trier de stl, puis insère, pyramidal, shaker et se termine par une bulle.
Rapide - 0,00225 ms
Insertion - 0,04482 ms
Heap - 0,07025 ms
Secousse - 0,14186 ms
Bulle - 0,14324 ms
En principe, les tableaux de données trop volumineux prennent beaucoup de temps à trier, mais quicksort gère des ordres de grandeur plus rapidement que d'autres.