Alpha 1/ボゴソート

Alpha 1

https://scratchpad.fandom.com/ja/wiki/Alpha_1

ボゴソート

ソースコード

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月

Alpha 1/ボゴソート

ボゴソート

ソースコード

C言語

実行結果

より大きな要素数

コメント投稿

Fan Feed