I rewrote the program code used in this article a couple of times. It was always interesting how much faster one sort would be than another. They seem to be passed by all students, but basically as a rewriting of a pseudo-algorithm in a lecture into a code in some language. Maybe this article will be useful for some novice programmer.
Let's consider 5 sorts. These are bubble, shake, heap, insertion and quick.
To analyze their speed, the clock () function will be used before sorting and after that, then their difference is taken and we find out the operating time of sorting. I used 100 iterations of 1000 values given in vectors and one sheet to test the built-in sort () function from stl. Each sort is given numbers equally scattered across the arrays at each iteration. After that, the time is written into the mean variable of each sorting and divided by the total by the number of iterations. So we find out the average running time of each sort and we can eventually compare them in speed with the same initial data. Data is entered into arrays using the rand () function.
Sorts.h file:
#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;
}
};
Note that you can use not only integers, but also real numbers and symbols.
Main program file:
#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;
}
What are the results?
With a large margin goes sort from stl, then inserts, pyramidal, shaker and ends with a bubble.
Quick - 0.00225 ms
Insertion - 0.04482 ms
Heap - 0.07025 ms
Shake - 0.14186 ms
Bubble - 0.14324 ms
In principle, too large data arrays take a long time to sort, but quicksort copes orders of magnitude faster than others.