#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <ctime>
#include <sys/time.h>
#include <fstream>
#include <math.h>
/*
* Visit : http://www.titrias.com/ultimate-sorting-algorithms-comparison/ for a complete comparison
*/
using namespace std;
int* b;
bool odd;
bool enablePrinting=false;
struct SortingAlgorithm{
string name;
long long time;
void (*algorithm)(int*,int);
};
//Selection Sort
void selectionSort(int* a, int size)
{
for (int i = 2; i < size; i++)
{
for (int j = i; j >= 1; j--)
{
if (a[j] < a[j - 1])
{
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
}
}
/////////////////////////////
//Insertion Sort
void insertionSort(int* a, int size)
{
for (int i = 1;i < size;i++)
{
int x = a[i];
int j = i;
while (j > 0 && a[j-1] > a[j])
{
int temporaryVariable=a[j];
a[j] = a[j-1];
a[j-1]=temporaryVariable;
j --;
}
a[j] = x;
}
}
/////////////////////////////
//Merge Sort
void merge(int* a, int first, int middle, int last)
{
int j,i0,i1;
i0 = first;
i1 = middle;
// While there are elements in the left or right runs
for (j = first; j < last; j++) {
// If left run head exists and is <= existing right run head.
if (i0 < middle && (i1 >= last || a[i0] <= a[i1])){
b[j] = a[i0];
i0++;
}
else{
b[j] = a[i1];
i1++;
}
}
}
///////////////////////////////
//Bubble Sort
void bubbleSort(int* a, int size) {
bool swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < size - j; i++) {
if (a[i] > a[i + 1]){
tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
swapped = true;
}
}
}
}
//////////////////////////////////
//Quick Sort
int partition(int* a, int top, int bottom)
{
int x = a[top];
int i = top - 1;
int j = bottom + 1;
int temp;
do
{
do
{
j--;
}while (x >a[j]);
do
{
i++;
} while (x <a[i]);
if (i < j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}while (i < j);
return j;
}
void _quickSort(int * a, int top, int bottom)
{
int middle;
if (top < bottom)
{
middle = partition(a, top, bottom);
_quickSort(a, top, middle);
_quickSort(a, middle+1, bottom);
}
return;
}
void quickSort(int * a, int size)
{
_quickSort(a,0,size);
return;
}
///////////////////////////////////////////////////////
void copyArray(int* a,int* b, int first, int last)
{
for(int k = first; k < last; k++)
a[k] = b[k];
}
void split(int* a, int first, int last)
{
if (last - first<2)
return;
int middle = floor((first + last) / 2);
//cout<<first<<" "<<middle<<" "<<last<<endl;
split(a, first, middle);
split(a, middle, last);
merge(a, first, middle, last);
copyArray(a,b, first, last);
}
void mergeSort(int *a, int size){
split(a,0,size);
}
/////////////////////////////
int* populateArray(int size)
{
b=new int[size];
int* a = new int[size];
for (int i = 0;i < size;i++)
{
a[i] = rand() % 50000;
b[i]=-1;
}
return a;
}
void printArray(int* a,int size)
{
for (int i = 0;i < size;i++)
{
if(enablePrinting)
cout<<a[i]<<" ";
}
if(enablePrinting)
cout<<endl;
}
long long now()
{
//LINUX ONLY.
struct timeval timeNow;
gettimeofday(&timeNow, NULL);
return (timeNow.tv_sec * 1000000 + timeNow.tv_usec);
}
int diff(timespec end, timespec start)
{
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.tv_sec;
}
SortingAlgorithm createSortingAlgorithm(string name,void (* f)(int*,int)){
SortingAlgorithm sortingAlgorithm;
sortingAlgorithm.name=name;
sortingAlgorithm.algorithm=f;
sortingAlgorithm.time=0;
return sortingAlgorithm;
}
int main()
{
int numberOfAlgorithms=5;
SortingAlgorithm* sortingAlgorithms=new SortingAlgorithm[numberOfAlgorithms];
sortingAlgorithms[0]=createSortingAlgorithm("Bubble",&bubbleSort);
sortingAlgorithms[1]=createSortingAlgorithm("Selection",&selectionSort);
sortingAlgorithms[2]=createSortingAlgorithm("Insertion",&insertionSort);
sortingAlgorithms[3]=createSortingAlgorithm("Merge",&mergeSort);
sortingAlgorithms[4]=createSortingAlgorithm("Quick",&quickSort);
int sizes[10] ={10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000};
long long start, end;
ofstream CFile ("comparison.csv");
CFile<<"SIZE;";
for( int k =0 ;k<numberOfAlgorithms;k++){
CFile<<sortingAlgorithms[k].name<<";";
}
CFile<<endl;
for (int i = 0;i < 10;i++)
{
srand(rand());
int size = sizes[i];
for (int j = 0;j < 1;j++)
{
for( int k =0 ;k<numberOfAlgorithms;k++){
int* a = populateArray(size);
start = now();
sortingAlgorithms[k].algorithm(a, size);
end = now();
sortingAlgorithms[k].time+= end- start;
}
}
CFile<<size<<";";
for( int k =0 ;k<numberOfAlgorithms;k++){
cout << sortingAlgorithms[k].name<<" " << size << " : " << sortingAlgorithms[k].time << endl;
CFile<<sortingAlgorithms[k].time<<";";
sortingAlgorithms[k].time=0;
}
CFile<<endl;
}
return 0 ;
}
原文在这里,什么都不说了,大写的服!
Ultimate Sorting Algorithms Comparison