C 9種類の並べ替えアルゴリズムを実現

アルゴリズム複雑度及び安定性分析
アルゴリズム名
へいきんじかん
ほじょくうかん
あんていせい
バブルソート
O(n2)
O(1)
はい
ソートの選択
O(n2)
O(1)
いいえ
ソートの挿入
O(n2)
O(1)
はい
下から上へ並べ替え
O(nlog2n)
O(n)
はい
上から下へ並べ替え
O(nlog2n)
O(n)
はい
クイックソート
O(nlog2n)
O(n)
いいえ
ヒープのソート
O(nlog2n)
O(1)
いいえ
ベースソート
O(dn)
O(rn)
はい
ヒルソート
\
O(1)
いいえ
ソートの時間効率比較
下図の表名は各種アルゴリズムが異なるデータ規模で並べ替えを完了するのに要する時間(ミリ秒単位)であり、表から明らかなようにO(n 2)の並べ替えアルゴリズムはO(nlog 2 n)のアルゴリズムより数百何千倍も時間が多く、データデータ規模が大きくなるにつれて間比も大きくなる.ソートされたデータはランダム数を採用するため、順序が乱され、高速ソートアルゴリズムは他のソートアルゴリズムより優れている.
 
アルゴリズム名
1万
2万
3万
4万
5万
6万
7万
8万
9万
10万
バブルソート
1442
5497
12206
21861
34017
49148
67394
88880
111939
139071
ソートの選択
199
816
1790
3254
5062
7166
9645
12636
16102
19643
ソートの挿入
178
717
1628
2882
4458
6446
8822
11649
14547
17914
下から上へ並べ替え
3
6
9
12
15
18
22
26
28
33
上から下へ並べ替え
3
7
11
15
18
23
27
31
36
40
クイックソート
2
5
8
11
14
18
21
25
29
32
ヒープのソート
3
7
12
16
19
23
26
30
34
37
ベースソート
9
21
30
40
49
59
66
75
90
98
ヒルソート
3
8
11
15
24
24
29
35
40
41
次はCコードです

#include <stdio.h>
#include <stdlib.h>

#define   LENGTH(s)   (sizeof(s)/sizeof(int))
#define   SWAP(x,y) {long t; t=x; x=y; y=t;}

//    
void BubbleSort(int **p,int len){
	int i,j;
	
	for(i=0;i<len;i++){//        
		for(j=0;j<len-i;j++){//      
			if((*p)[j]>(*p)[j+1]){
				SWAP((*p)[j],(*p)[j+1]);
			}
		}
	}
}

//    
void SelectSort(int **p,int len){
	int i,j,k;
	
	for(i=0;i<len;i++){
		k=i;
		for(j=i+1;j<len;j++){
                if((*p)[k]>(*p)[j]){
            		k=j;   
                }
		}
		if(k!=i){
			SWAP((*p)[k],(*p)[i]);
		}
	}
	
}

//    
void InsertSort(int **p,int len){
	int i,j,k;
	
	for(i=1;i<len;i++){
		k=(*p)[i];
		for(j=i-1;j>=0;j--){
			if((*p)[j]>k){
				(*p)[j+1]=(*p)[j];
            }else{
				break;
			}
		}
		(*p)[j+1]=k;
	}
}

//    
void QuickSort(int **p,int min,int max){
	int i,j,k;
	if(min<max){
		i=min;j=max;k=(*p)[i];
		while(i<j){
			while(i<j && (*p)[j]>k)
				j--;
			if(i<j)
				(*p)[i++]=(*p)[j];

			 while(i<j && (*p)[i]<k)
				i++;
			 if(i<j)
				(*p)[j--]=(*p)[i];
		}
		(*p)[i]=k;
		QuickSort(p,min,i-1);
		QuickSort(p,i+1,max);
	}
}

void main(){
	int arr[]={1233,22,38,99,90,1,23,45,394,2,384,45,100,-10,22};
	int i,*p=arr;
	int len=LENGTH(arr);
	//BubbleSort(&p,len);
	//SelectSort(&p,len);
	//InsertSort(&p,len);
	QuickSort(&p,0,len);
	for(i=0;i<len;i++){
		printf("%d
",arr[i]);
	}
}