この記事で使用したプログラムコードを数回書き直しました。ある種類が別の種類よりどれだけ速いかは常に興味深いものでした。それらはすべての学生に渡されているようですが、基本的には講義の疑似アルゴリズムをある言語のコードに書き直したものです。たぶん、この記事は一部の初心者プログラマーにとって役立つでしょう。
5種類を考えてみましょう。これらは、バブル、シェイク、ヒープ、挿入、およびクイックです。
それらの速度を分析するために、ソートの前にクロック（）関数を使用し、その後、それらの差を取得して、ソートの動作時間を調べます。ベクトルと1枚のシートで指定された1000個の値を100回繰り返して、stlの組み込みのsort（）関数をテストしました。各ソートには、各反復で配列全体に均等に分散された番号が与えられます。その後、時間は各ソートの平均変数に書き込まれ、合計を反復回数で除算されます。したがって、各ソートの平均実行時間を見つけて、最終的に同じ初期データと速度を比較できます。データは、rand（）関数を使用して配列に入力されます。
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;
}
};
整数だけでなく、実数や記号も使用できることに注意してください。
メインプログラムファイル：
#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;
}
結果はどうなりますか？
マージンが大きいと、stlからソートされ、挿入、ピラミッド、シェーカー、そしてバブルで終わります。
クイック-0.00225ミリ秒
挿入-0.04482ミリ秒
ヒープ-0.07025ミリ秒
シェイク-0.14186ミリ秒
バブル-0.14324ミリ秒
原則として、大きすぎるデータ配列はソートに時間がかかりますが、クイックソートは他の配列よりも桁違いに高速に処理します。