小さい実験,4種類の並べ替えアルゴリズムの性能の比較

暇な時は大丈夫です.小さなテストをして、泡をテストして、選択して、挿入して、高速の4つのソートをして、同じ100000個の要素を含む配列をソートするのにかかる時間を比較します.
4つのソートのコードは次のとおりです.
泡のソート:

template <typename T>
void bubble_sort(T a[], int num){
	if(num ==0 || num == 1)
		return ;
	bool changed = false;
	do{
		for(int i=0; i<num-1; i++){
			if(a[i] < a[i+1]){
				swap(a[i], a[i+1]);
				changed = true;
			}
		}
		
	}while(changed);
}

 
ソートを選択:

template <typename T>
void select_sort(T a[], int num){
	T min;
	int locate;// 
	for(int i=0; i<num-1; i++){
		min = a[i];
		// 
		for(int j=i+1; j<num; j++){
			if(a[j] < min){
				locate = j;
			}
		}
		swap(a[i], a[locate]);
	}
}

 
ソートの挿入:

template <typename T>
void insert_sort(T a[], int num){
	int j;
	int temp;// 
	for(int i=1; i<num; ++i){
		j = i;
		temp = a[i];
		// 
		while(j > 0 && temp < a[j-1]/* */){
			// 
			a[j] = a[j-1];
			// 
			--j;
		}
		// 
		a[j] = temp;
	}
}

 
クイックソート:

template <typename T>
void quick_sort(T a[], int num)
{
	// ， 
	if(num ==1)
		return ;
	// 
	if(num == 2){
		if(a[1] < a[0])
			swap(a[1], a[0]);
		return ;
	}
	// ， 
	swap(a[num/2], a[0]);
	T bound = a[0];
	// 
	T* L = a+1;
	T* R = a+num-1;
	// ， ， 
	while(L < R){
		while(L < R && *L < bound)
			++L;
		while(R >= L && *R > bound)
			--R;
		if(L < R)
			swap(*L, *R);
	}
	if(*R < bound)
		swap(*R, *a);
	// 
	quick_sort(a, R-a);
	quick_sort(R+1, num-1-(R-a));
}

 
テスト手順は次のとおりです.

#include <iostream>
using namespace std;
#include <ctime>

int main()
{
	const int N=100000;
	int a[N];
	while(1){	
		for(int i=0; i<N; i++)
			a[i] = N-i;
		int choice;
		cout<<"1.bubble 2.insert 3.select 4.quick"<<endl;
		clock_t t1;
		clock_t t2;
		cin >> choice;
		switch(choice)
		{
			case 1:
				t1 = clock();
				bubble_sort(a, N);
				t2 = clock();
				break;
			case 2:
				t1 = clock();
				insert_sort(a, N);
				t2 = clock();
				break;
			case 3:
				t1 = clock();
				select_sort(a, N);
				t2 = clock();
				break;
			case 4:
				t1 = clock();
				quick_sort(a, N);
				t2 = clock();
				break;
		}
		cout << double(t2-t1)/CLOCKS_PER_SEC << endl;
	}	
	return 0;
}

 
テスト結果は下図の通りです.
上図から分かるように、速列は確かに速く、泡が出て無言で、挿入は選択より少し速い.