Ich habe den in diesem Artikel verwendeten Programmcode einige Male umgeschrieben. Es war immer interessant, wie viel schneller eine Sorte als eine andere sein würde. Sie scheinen von allen Studenten bestanden zu werden, aber im Grunde genommen als Umschreiben eines Pseudoalgorithmus in einer Vorlesung in einen Code in einer Sprache. Vielleicht ist dieser Artikel für einige unerfahrene Programmierer nützlich.
Betrachten wir 5 Sorten. Dies sind Bubble, Shake, Heap, Insertion und Quick.
Um ihre Geschwindigkeit zu analysieren, wird die Funktion clock () vor dem Sortieren verwendet. Danach wird ihre Differenz genommen und die Betriebszeit des Sortierens ermittelt. Ich habe 100 Iterationen von 1000 Werten in Vektoren und einem Blatt verwendet, um die eingebaute Funktion sort () von stl zu testen. Jede Sortierung erhält bei jeder Iteration Nummern, die gleichmäßig über die Arrays verteilt sind. Danach wird die Zeit in die mittlere Variable jeder Art geschrieben und durch die Summe durch die Anzahl der Iterationen geteilt. So ermitteln wir die durchschnittliche Laufzeit jeder Sorte und können sie schließlich in der Geschwindigkeit mit denselben Anfangsdaten vergleichen. Daten werden mit der Funktion rand () in Arrays eingegeben.
Sorts.h-Datei:
#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;
}
};
Beachten Sie, dass Sie nicht nur Ganzzahlen, sondern auch reelle Zahlen und Symbole verwenden können.
Hauptprogrammdatei:
#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;
}
Was sind die Ergebnisse?
Mit einem großen Rand geht sort von stl, dann Einsätze, Pyramiden, Shaker und endet mit einer Blase.
Schnell - 0,00225 ms Einfügen
- 0,04482 ms
Heap - 0,07025 ms
Schütteln - 0,14186 ms
Blase - 0,14324 ms
Im Prinzip dauert das Sortieren zu großer Datenfelder lange, aber das Quicksortieren bewältigt Größenordnungen schneller als andere.