並べ替えアルゴリズムの時間効率に関する小さな実験

6829 ワード
昨日、友达のパソコンでテストしました:直接ソートに挿入して、見張りを設置してプログラムの効率を高めることができますか?
当时使用したJAVAコードテストの结果、设置歩哨は意外にも速度が遅くて、私は歩哨のこの最适化をプラスしてプログラムの効率を高めることができると思って、そこで下りて自分で少しの実験をしてテストの検证をしました
テストするすべてのソートの関数コードを含むヘッダー・ファイル:
//sort.h
//    a[0,1...n] a[1],a[2],...,a[n] n    ,a[0]   
//      ，    ，      ，           ，    ，   
//2012.8.9 cc
#ifndef _SORT_H_
#define _SORT_H_


//    
void maopao(int arr[],int n){
	int temp ;
	for(int i=1; i<=n; i++){
		for(int j=i+1; j<=n; j++){
			if(arr[i] > arr[j]){
				temp = arr[i] ;
				arr[i] = arr[j];
				arr[j] = temp ;
			}
		}
	}
}

//      
void InsertSortA(int arr[],int n){
	int i,j,t;
	for(i=1; i<=n; i++){
		t = arr[i] ;
		for(j=i-1; j>=0; j--){
			if(t<arr[j]){
				arr[j+1] = arr[j];
			}else{
				break;
			}
		}
		//j    
		arr[j+1] = t ;//j+1    。
	}
}

//           
void InsertSortB(int arr[],int n){
	int i,j ;
	for(i=2; i<=n; i++){
		if(arr[i]<arr[i-1]){
			arr[0] = arr[i] ;
			arr[i] = arr[i-1] ;
			j = i-2 ;
			while(arr[0]<arr[j]){
				arr[j+1] = arr[j] ;
				j-- ;
			}
			arr[j+1] = arr[0] ;
		}
	}
}

//    
void SelectSort(int arr[],int n){
	int flag = 0 ;
	int temp = 0 ;
	for(int i=0; i<=n; i++){
		flag = i ;
		for(int j=i+1; j<=n; j++){
			if(arr[flag] > arr[j]){
				flag = j ;
			}
		}
		 temp = arr[i] ;
		 arr[i] = arr[flag] ;   
		 arr[flag] = temp ;
	}
}

//    
static int Partition(int arr[],int low,int high){
	arr[0]=arr[low];
	int pivokey=arr[low];
	while(low<high){
		while(low<high && arr[high]>=pivokey)
			--high;
		arr[low]=arr[high];
		while(low<high && arr[low]<=pivokey)
			++low;
		arr[high]=arr[low];
	}
	arr[low]=arr[0];
	return low;
}
void QSort(int arr[],int low,int high){
	int pivotloc;
	if(low<high){
		pivotloc=Partition(arr,low,high);
		QSort(arr,low,pivotloc-1);
		QSort(arr,pivotloc+1,high);
	}
}

//   
static void HeapAdjust(int arr[],int s,int m){
	int rc=arr[s];
	for(int j=s*2;j<=m;j*=2){
		if(j<m && arr[j]<arr[j+1])
			++j;
		if(rc>=arr[j])
			break;
		arr[s]=arr[j];
		s=j;
	}
	arr[s]=rc;
}
void HeapSort(int arr[],int length){
	int temp;
	for(int i=length/2;i>0;--i)
		HeapAdjust(arr,i,length);
	for(int i=length;i>1;--i){
		//swap(a[1],a[i]);
		temp=arr[1];
		arr[1]=arr[i];
		arr[i]=temp;

		HeapAdjust(arr,1,i-1);
	}
}

//    


#endif

Windowsプラットフォームでは、すべてのソートアルゴリズムの時間効率をC方式clock()で測定します.
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include "sort.h"

#define LENGTH 30000

int main(){
	int a[6][LENGTH+1];
	for(int times=0;times<10;times++){
		a[0][0]=a[1][0]=a[2][0]=a[3][0]=a[4][0]=a[5][0]=0;
		srand((unsigned int)time(NULL));
		for(int i=1;i<=LENGTH;i++){
			a[0][i]=a[1][i]=a[2][i]=a[3][i]=a[4][i]=a[5][i]=rand()%LENGTH;
		}

		clock_t tm[7];
		tm[0]=clock();
		InsertSortA(a[0],LENGTH);
		tm[1]=clock();
		InsertSortB(a[1],LENGTH);
		tm[2]=clock();
		maopao(a[2],LENGTH);
		tm[3]=clock();
		SelectSort(a[3],LENGTH);
		tm[4]=clock();
		QSort(a[4],1,LENGTH);
		tm[5]=clock();
		HeapSort(a[5],LENGTH);
		tm[6]=clock();

		printf("InsertSortA:%dms
",tm[1]-tm[0]);
		printf("InsertSortB:%dms
",tm[2]-tm[1]);
		printf("MaopaoSort:%dms
",tm[3]-tm[2]);
		printf("SelectSort:%dms
",tm[4]-tm[3]);
		printf("QuickSort:%dms
",tm[5]-tm[4]);
		printf("HeapSort:%dms
",tm[6]-tm[5]);
		
		putchar('
');

	}
	return 0;
}

実験結果は以下の通りである.
InsertSortA:1501ms InsertSortB:1318ms MaopaoSort:4906ms SelectSort:2269ms QuickSort:8ms HeapSort:9ms InsertSortA:1481ms InsertSortB:1368ms MaopaoSort:5436ms SelectSort:2357ms QuickSort:21ms HeapSort:11ms InsertSortA:1569ms InsertSortB:1430ms MaopaoSort:5169ms SelectSort:2252ms QuickSort:7ms HeapSort:9ms InsertSortA:1645ms InsertSortB:1826ms MaopaoSort:5598ms SelectSort:2323ms QuickSort:10ms HeapSort:10ms InsertSortA:1546ms InsertSortB:1322ms MaopaoSort:4829ms SelectSort:2272ms QuickSort:7ms HeapSort:10ms InsertSortA:1474ms InsertSortB:1316ms MaopaoSort:4661ms SelectSort:2258ms QuickSort:8ms HeapSort:10ms InsertSortA:1467ms InsertSortB:1329ms MaopaoSort:4818ms SelectSort:2172ms QuickSort:8 ms HeapSort:9 ms InsertSortA:1455 ms InsertSortB:1289 ms MaopaoSort:46621 ms SelectSort:172 ms QuickSort:7 ms HeapSort:9 ms InsertSortA:1422 ms InsertSortB:14422 ms InsertSortB:1279 ms MaopaoSort:4602 ms SelectSort:21177 ms QuickSort:7 ms QuickSort:7 ms HeapSort:7 ms HeapSort:9 ms InsertSortA:1440 ms InsertSortA:1440 ms InsertSortB:14250 ms MaopaoSortB:14250 ms MaopaoSort:4254 54 ms lectSort:2157 ms QuickSort:8 ms HeapSort:9 msどうぞ意键继续....
LINUXプラットフォームではtimeval構造体を用い,gettimeofdayを用いてより精度の高い実験結果を試験した.
//    a[0,1...n] a[1],a[2],...,a[n] n    ,a[0]   
//      ，                     


// timeval  ，gettimeofday        

#include <sys/time.h>
#include <time.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include "sort.h"

#define LENGTH 30000


int main(){
	int a[2][LENGTH+1];
	for(int times=0;times<10;times++){
		a[0][0]=a[1][0]=0;
		srand(time(NULL));
		for(int i=1;i<=LENGTH;i++){
			a[0][i]=a[1][i]=rand()%LENGTH;
		}

		struct timeval tm[3];
		gettimeofday(&(tm[0]),NULL);
		InsertSortA(a[0],LENGTH);
		gettimeofday(&(tm[1]),NULL);
		InsertSortB(a[1],LENGTH);
		gettimeofday(&(tm[2]),NULL);

		printf("InsertSortA:%ld*10E-6s
",((tm[1].tv_sec-tm[0].tv_sec)*1000000+(tm[1].tv_usec-tm[0].tv_usec)));
		printf("InsertSortB:%ld*10E-6s
",((tm[2].tv_sec-tm[1].tv_sec)*1000000+(tm[2].tv_usec-tm[1].tv_usec)));

		putchar('
');

	}
	return 0;
}
実験結果は以下の通りである.
cc@ubuntu:~/デスクトップ/test$gcc insert 2.c -o b.out -std=c99 cc@ubuntu:~/デスクトップ/test$./b.out InsertSortA:1424454*10E-6s InsertSortB:1312852*10E-6s InsertSortA:1425278*10E-6s InsertSortB:1315860*10E-6s InsertSortA:1420455*10E-6s InsertSortB:1310364*10E-6s InsertSortA:1432156*10E-6s InsertSortB:1325098*10E-6s InsertSortA:1444255*10E-6s InsertSortB:1413137*10E-6s InsertSortA:1600424*10E-6s InsertSortB:1317670*10E-6s InsertSortA:1568105*10E-6s InsertSortB:1420736*10E-6s InsertSortA:1484553*10E-6s InsertSortB:1433338*10E-6s InsertSortA:1436134*10E-6s InsertSortB:1324259*10E-6s InsertSortA:1432738*10E-6s InsertSortB:1325463*10E-6s cc@ubuntu:~/デスクトップ/test$
実験から得られた:
1.LINUXプラットフォーム、Windowsプラットフォーム、下に30000個の数を直接挿入して並べ替え、見張りのある時間効率がもっと高い
2.clock()方式測定時間の場合、精度は1 msであり、gettimeofday()方式の精度はusレベルに達する
3.ソートおよびバブルソートを選択する時間効率は、高速ソートおよびスタックソートよりもはるかに低く、高速ソートはスタックソートよりも弱く、
ははは、さっき小さな収穫がありました:試験結果はすべてコンソールに印刷されて、どのようにコンソールが印刷した文字をコピーしますか?方法は次のとおりです.
マウスの右ボタン->タグ->コピーする内容を選択->戻るボタンで選択した内容をコピーします^^;
CentOS6.7にTensorFlowをインストールする
[セットトップ]Java JDBCトランザクションメカニズム