FANDOM


ボゴソート

ソースコード

C言語

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
#define BUFSIZE 20
 
void init_array(int *array, const unsigned int array_size);
void bogosort(int *array, const unsigned int array_size);
int is_sorted(int *array, const unsigned int array_size);
void shuffle(int *array, const unsigned int array_size);
 
int main(void)
	{
	clock_t start, end;
	int *array, repeat;
	unsigned int array_size;
	char buf[BUFSIZE];
	double exec_time = 0;
 
	printf("input array size:");
	fgets(buf, sizeof(buf), stdin);
	array_size = (unsigned int)atoi(buf);
 
	printf("input number of executing:");
	fgets(buf, sizeof(buf), stdin);
	repeat = atoi(buf);
 
	if((array = malloc(sizeof(int)*array_size)) == NULL)
		{
		fprintf(stderr, "Error:Mamory Allocation Fault.");
 
		exit(1);
		}
 
	srand(time(NULL));
 
	while(repeat > 0)
		{
		init_array(array, array_size);
 
		start = clock();
		bogosort(array , array_size);
		end = clock();
 
		exec_time += (double)(end - start)/CLOCKS_PER_SEC;
 
		repeat--;
		}
 
	printf("Execution Time:%lf [sec.]\n", exec_time);
 
	free(array);
 
	return 0;
	}
 
 
void init_array(int *array, const unsigned int array_size)
	{
	unsigned int n = array_size;
 
	while(n > 0)
		{
		array[n-1] = rand();
 
		n--;
		}
	}
 
void bogosort(int *array, const unsigned int array_size)
	{
	while(!is_sorted(array, array_size)) shuffle(array, array_size);
	}
 
int is_sorted(int *array, const unsigned int array_size)
	{
	unsigned int n = array_size;
	unsigned char sorted = 1;
 
	while(n > 1)
		{
		if(array[n-1] < array[n-2]) sorted = 0;
 
		n--;
		}
 
	return sorted;
	}
 
void shuffle(int *array, const unsigned int array_size)
	{
	unsigned int n = array_size, k, tmp;
 
	while(n > 1)
		{
		k = rand()%n;
		n--;
		tmp = array[n];
		array[n] = array[k];
		array[k] = tmp;
		}
	}

実行結果

要素数 実行回数 処理時間
[sec.]
処理時間増加率
[倍]
実測 標準化
[sec./10,000,000 exec.]
実測 理想
2 10,000,000 1.0490 1.0490 --- ---
3 10,000,000 5.7180 5.7180 5.45 4.5
4 10,000,000 35.840 35.840 6.27 5.33
5 1,000,000 23.907 239.07 6.67 6.25
6 500,000 90.203 1804.06 7.55 7.2
7 100,000 149.594 14959.4 8.29 8.17
8 10,000 143.532 143532 9.59 9.14

より大きな要素数

要素数 実行回数 処理時間
[sec.]
処理時間増加率
[倍]
実測 標準化
[sec./exec.]
実測 理想
10 100 180.844 1.80844 --- ---
11 10 226.703 22.6703 12.5 12.1
12 1 138.282 138.282 6.10 13.1

2009/03/17 05:00

プロフィール
  • 名前:Tommy6
  • ニックネーム:( ・ω・)
  • 性別:男
  • 生年月日:
  • 出身地:北
  • 血液型:B
2009年03月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
最近の記事

Extension:DynamicPageList (DPL), version 2.3.0 : Error: No selection criteria found! You must use at least one of the following parameters: category, namespace, titlematch, linksto, uses, createdby, modifiedby, lastmodifiedby or their 'not' variants

アーカイブ

Extension:DynamicPageList (DPL), version 2.3.0 : Error: No selection criteria found! You must use at least one of the following parameters: category, namespace, titlematch, linksto, uses, createdby, modifiedby, lastmodifiedby or their 'not' variants

YouTube






編集

まだ今月分のポータルが作成されていません!

作成

まだ本日分のポータルが作成されていません!

作成

日記を書く

注意:トップページからのみ日記を作成してください。他のページから作ると記事空間がおかしくなります。

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki