よく使われるソートアルゴリズムのc++実装(バブル,選択,挿入,スタック,shell,高速,集計)とsort()の比較
たまたま本で「C++プログラマーに喜んでもらったことは、sort()がc言語のquicksortを全面的に打ち負かすこと」という言葉を見たので、自分でテストすることにしました.ちょうど他のランキングも一緒にテストして、当初書いていなかった補償としましょう.
テストファイルの説明:
1、テスト中に配列を使うと、MAXが1000000に達するとstack overになるので、ここではすべてvectorを使っています.
2、乱数は1つのグローバルvectorで保存し、単独でソートするときは直接vectorv(orited)であるが、これについてはc++は確かに便利である.再帰呼び出しがあるため、呼び出し中にvectorがどれだけ大きいかは確定せず、配列でどのように初期化するかが問題となっている.
3、テストソートの関数名はすべて下線分割の方式で、例えばselect_sort().
4、ソート結果は書き込みファイルによって検証された.
5、ファイルはwin 7、vs 6、vs 08、およびgccでコンパイルされた.vs 08では、最初に使用したファイルの操作をFILEで行うと、エラーが発生し、streamに変更することができます.例えば、開いたり空にしたりして、以下のように変更することができます.
ip >> temp;
v.push_back(temp);すぐ
最終的に変更された標準c++テストファイルは以下の通りです.
sort()については、ここではデフォルトで昇順に並べられていますが、降順に並べたい場合は、関数を追加できます.
プログラムのmainセクションでは、shellがあまり参照されていないテスト結果の一部が示されています.そこで列がない(本の原語で言えば、shellソートの分析は複雑な問題であり、時間は取得したインクリメンタルシーケンスの関数であり、数学的にまだ解決されていない問題に関連している).ソート結果をファイルに保存して見ると、shellの結果は、高速ソートのように完全に正確ではなく、確率の問題であることがわかる.
vc 6のテスト結果は以下の通りです.
Sort()
Quick
Bubble
Select
Merge
Shell
heap
insert
1k
0
1
78
35
107
14
2
21
1w
2
12
4883
3099
7947
1135
34
2274
10w
26
142
410630
385299
774607
108289
267
220359
vs 08でのテスト結果は以下の通りです:(vs 08ではinsertに一部エラーがあるため、リストされていません)
Sort()
Quick
Bubble
Select
Merge
Shell
heap
1k
26
2
193
291
15
90
8
1w
302
29
12674
8203
216
3010
57
10w
3624
378
1.02754e+006
804142
804142
804142
713
gccでのテスト結果:
Sort()
Quick
Bubble
Select
Merge
Shell
heap
insert
1k
0
0
9
3
1
2
1
2
1w
2
3
725
452
81
170
4
294
10w
29
27
55812
34269
4390
16272
45
28208
統計結果はもちろん明らかですが、vs 08ではsort()は確かに一般的な速さではありません(特にvc 6では圧倒的に優れています)、続いてquicksortとheapsortです.heapsortについては、ここのスタックは、直接順番で表示されており、時間も少なくありません.
不思議なことにvc 6の下のmergeは意外にも泡が出るよりも遅くて、天理がありませんか、もちろんgccのような標準的なc++テストが私たちに自信を与えました.
統計が終わったばかりで挿入していないことに気づいて、統計結果を補充して、今のところそうでしょう.何か間違っていることがあったら、フォローして修正してください.
後記:後に双方向の泡を変えて、元の泡より倍以上速く、選択よりもやや速いことが分かった(後にテストして、最初の書き方が間違っていたが、実は一方向の泡の速度と同じだった)
コードは次のとおりです.
実行時間結果がすぐに更新されます
選択を双方向選択に変えようと思っていたが、minは低位、maxは高位、2サイクル目j
テストファイルの説明:
1、テスト中に配列を使うと、MAXが1000000に達するとstack overになるので、ここではすべてvectorを使っています.
2、乱数は1つのグローバルvectorで保存し、単独でソートするときは直接vector
3、テストソートの関数名はすべて下線分割の方式で、例えばselect_sort().
4、ソート結果は書き込みファイルによって検証された.
5、ファイルはwin 7、vs 6、vs 08、およびgccでコンパイルされた.vs 08では、最初に使用したファイルの操作をFILEで行うと、エラーが発生し、streamに変更することができます.例えば、開いたり空にしたりして、以下のように変更することができます.
FILE *fp =fopen("data.txt","wr");
ofstream fp("data.txt");if (fp==NULL)
if (fp.fail())ip >> temp;
v.push_back(temp);すぐ
fp << orited[i] << " ";// ，
fprintf(fp,"%d ",orited[i]);
//
// fclose(fp);
fp.close();最終的に変更された標準c++テストファイルは以下の通りです.
//============================================================================
// Name : sort.cpp
// Author : xia
// Version : 1.0
// Copyright : NUAA
// Description : ( ， ， ， ， ， algorithm sort)
//============================================================================
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <ctime>
using namespace std;
const int MAX = 1000;// MAX ， stack overflow, vector
vector<int> orited;// vector
void randNum()
{// vector
ofstream fp("data.txt");
if (fp.fail())
{
cout << "open data error " << endl;
exit(EXIT_FAILURE);
}
srand((unsigned)time(NULL));
for (int i=0 ; i<MAX ; i++)
{
orited.push_back(rand()); // vector
fp << orited[i] << " ";
}
fp.close();
}
/************************************************************************/
/* */
/************************************************************************/
int Partion(vector<int> &v ,int low ,int high)
{// vector ，
int pivotkey;
pivotkey = v[low] ;
while ( low < high )
{
while (low < high && v[high] >= pivotkey)
high -- ;
v[low] = v[high];
while (low < high && v[low] <= pivotkey )
low ++ ;
v[high] = v[low];
}
v[low] = pivotkey ;
return low ;
}
void quickSort(vector<int> &number ,int left ,int right)
{// ，
if ( left < right )
{
int i = Partion(number , left, right) ;
quickSort(number, left, i-1); //
quickSort(number, i+1, right); //
}
}
void quick_sort()
{//
double start ,end ;
vector<int> v(orited);// orited v
start = clock() ;
quickSort(v,0,MAX-1);
end = clock();
cout << "quick sort cost : " << end - start << endl;
}
/************************************************************************/
/* */
/************************************************************************/
void InsertSort(vector<int> &v)
{ // vector
int i,j;
int key;
for(i=1 ; i < v.size() ; i++)
if ( v[i] < v[i-1] )// "<", v[i]
{
key = v[i];
for( j=i-1 ; key < v[j] ; j-- )
v[j+1] = v[j]; //
v[j+1] = key; //
}
}
void insert_sort()
{
vector<int> v(orited);
double start ,end;
start = clock();
InsertSort(v);
end = clock();
cout << "insert sort cost : " << end - start << endl;
}
/************************************************************************/
/* algorithm sort */
/************************************************************************/
void vector_sort()
{
double start ,end ;
vector<int> v(orited);
start = clock();
sort(v.begin(),v.end());
end = clock();
cout << "vector sort cost : " << end - start << endl;
}
/************************************************************************/
/* */
/************************************************************************/
void bubble_sort()
{
int i,j;
vector<int> v(orited);
double start ,end;
start = clock();
for ( i=0 ; i< MAX ; i++)
{
for (j=i+1 ; j< MAX ; j++)
{
if (v[i] > v[j])//
{
swap(v[i],v[j]);
}
}
}
end = clock();
cout << "bubble sort cost : " << end - start << endl;
}
/************************************************************************/
/* */
/************************************************************************/
void select_sort()
{
int i,j,min;
vector<int> v(orited);
double start ,end;
start = clock();
for (i=0 ; i< MAX ; i++)
{
min = i ;
for (j=i+1 ; j<MAX ; j++)
{
if (v[j] < v[min])
min = j;
}
if (min != i)
swap(v[i],v[min]);
}
end = clock();
cout << "select sort cost : " << end - start << endl;
}
/************************************************************************/
/* */
/************************************************************************/
void Merge(vector<int> &array,int start ,int mid ,int end)
{// vector start-mid mid-end
int j,k,l;
vector<int> temp(array); // temp， array
for( j=mid+1,k=start ; start<=mid&&j<=end ; k++ )
{
if ( temp[start] < temp[j] )
array[k] = temp[start++];
else
array[k] = temp[j++];
}
if( start <= mid )
{
for( l=0 ; l <= mid-start ; l++)
array[k+l] = temp[start+l]; // 0 min-start array
}
if( j <= end )
{
for( l=0 ; l<=end-j ; l++ )
array[k+l]= temp[j+l]; // j end array
}
}
void MergeSort( vector<int> &v, int low ,int high )
{
if (low < high)
{
int mid = ( low + high )/2; //
MergeSort( v , low , mid ); //
MergeSort( v , mid+1 , high ); //
Merge( v , low , mid , high ) ; //
}
}
//
void merge_sort()
{
vector<int> v( orited );
double start ,end;
start = clock();
MergeSort(v,0,MAX-1);
end = clock();
cout << "merge sort cost : " << end - start << endl;
}
/************************************************************************/
/* */
/************************************************************************/
const int SORTCOUNT = 20;//
const int dlta[SORTCOUNT] = {2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3};//
void ShellInsert(vector<int> &v , int dk)
{// v shell ， dk， 1；j<=0 ，
int i,j;
for ( i=dk ; i < v.size() ; i++)
{
if (v[i] < v[i-dk])
{
int temp = v[i];//
for (j=i-dk ; j>0 && temp < v[j] ; j -= dk)
v[j+dk] = v[j] ;// ，
v[j+dk] = temp; //
}
}
}
void ShellSort(vector<int> &v ,const int dlta[] ,int t)
{//
for (int k=0 ; k < t ; k++)
ShellInsert(v,dlta[k]) ;// dlta[k]
}
void shell_sort()
{
vector<int> v( orited );
double start ,end;
start = clock();
ShellSort(v,dlta,SORTCOUNT);
end = clock();
cout << "shell sort cost : " << end - start << endl;
}
/************************************************************************/
/* */
/************************************************************************/
void HeapAdjust(vector<int> &v ,int s ,int m)// ， vector
{//
int rc,j;
rc = v[s];
for ( j=2*s ; j<= m ; j *= 2 )
{// key
if (j<m && v[j] < v[j+1])
j++ ;//j key
if ( rc >= v[j] )
break;// rc s
v[s] = v[j] ;
s = j;
}
v[s] = rc ; //
}
void HeapSort(vector<int> &v)
{ // vector
int t , i;
for( i=v.size()/2 ; i>0 ; i--) // v
HeapAdjust( v,i,v.size()-1 );
for( i=v.size()-1 ; i>0 ; i-- )
{// [0..i]
t = v[0];
v[0] = v[i];
v[i] = t ;
HeapAdjust(v,0,i-1); // v[0..i-1]
}
}
//
void heap_sort()
{
vector<int> v( orited );
double start ,end;
start = clock();
HeapSort(v);
end = clock();
cout << "heap sort cost : " << end - start << endl;
}
int main(int argc, char* argv[])
{
randNum(); // MAX， ， vector
vector_sort();
quick_sort();
bubble_sort();
select_sort();
merge_sort();
shell_sort();
heap_sort();
insert_sort();
return 0;
}
sort()については、ここではデフォルトで昇順に並べられていますが、降順に並べたい場合は、関数を追加できます.
bool compare(int a ,int b)
{
return a>b;//a>b a<b
} sort(v.begin(),v.end(),compare);プログラムのmainセクションでは、shellがあまり参照されていないテスト結果の一部が示されています.そこで列がない(本の原語で言えば、shellソートの分析は複雑な問題であり、時間は取得したインクリメンタルシーケンスの関数であり、数学的にまだ解決されていない問題に関連している).ソート結果をファイルに保存して見ると、shellの結果は、高速ソートのように完全に正確ではなく、確率の問題であることがわかる.
vc 6のテスト結果は以下の通りです.
Sort()
Quick
Bubble
Select
Merge
Shell
heap
insert
1k
0
1
78
35
107
14
2
21
1w
2
12
4883
3099
7947
1135
34
2274
10w
26
142
410630
385299
774607
108289
267
220359
vs 08でのテスト結果は以下の通りです:(vs 08ではinsertに一部エラーがあるため、リストされていません)
Sort()
Quick
Bubble
Select
Merge
Shell
heap
1k
26
2
193
291
15
90
8
1w
302
29
12674
8203
216
3010
57
10w
3624
378
1.02754e+006
804142
804142
804142
713
gccでのテスト結果:
Sort()
Quick
Bubble
Select
Merge
Shell
heap
insert
1k
0
0
9
3
1
2
1
2
1w
2
3
725
452
81
170
4
294
10w
29
27
55812
34269
4390
16272
45
28208
統計結果はもちろん明らかですが、vs 08ではsort()は確かに一般的な速さではありません(特にvc 6では圧倒的に優れています)、続いてquicksortとheapsortです.heapsortについては、ここのスタックは、直接順番で表示されており、時間も少なくありません.
不思議なことにvc 6の下のmergeは意外にも泡が出るよりも遅くて、天理がありませんか、もちろんgccのような標準的なc++テストが私たちに自信を与えました.
統計が終わったばかりで挿入していないことに気づいて、統計結果を補充して、今のところそうでしょう.何か間違っていることがあったら、フォローして修正してください.
後記:後に双方向の泡を変えて、元の泡より倍以上速く、選択よりもやや速いことが分かった(後にテストして、最初の書き方が間違っていたが、実は一方向の泡の速度と同じだった)
コードは次のとおりです.
for (i=0 ; i< MAX ; i++)
{
k = MAX-i-1;
for (j=i+1 ; j< k ; j++)//
{
if (v[j] < v[i])
{
swap(&v[i],&v[j]);
}
if (v[MAX-j-1] > v[k])
{
swap(v[MAX-j-1],v[k]);
}
}
}実行時間結果がすぐに更新されます
選択を双方向選択に変えようと思っていたが、minは低位、maxは高位、2サイクル目j