Author: Dann Corbit
Date: 13:37:15 10/19/99
Go up one level in this thread
On October 19, 1999 at 15:20:26, J. Wesley Cleveland wrote:
[snip]
>I came up with an even slower sort.
>
>while (!sorted) ;
However, that algorithm never succeeds. Bogosort provably does succeed, it just
takes a long, long time. Here it is, for those interested in the macabe:
/* A BogoSort(tm) implementation bsort(), like qsort()
Public domain by Tom Torfs
Define TEST for a demonstration */
#include <stdlib.h>
#include <time.h>
/* This BogoSort(tm) routine performs very
well for an already sorted set of data */
void bsort(void *base,
size_t nmemb,
size_t size,
int (*compar)(const void *, const void *))
{
static int seeded = 0;
size_t elem1, elem2;
size_t count;
unsigned char temp;
unsigned char *cbase = base;
int sorted;
/* seed PRNG if first call */
if (!seeded)
{
srand((unsigned)time(NULL));
seeded = 1;
}
/* less than 2 elements are always sorted */
if (nmemb < 2)
return;
for (;;)
{
/* check if sorted */
sorted = 1;
for (elem1=0; elem1<nmemb-1; elem1++)
{
if (compar((const void *)(cbase+elem1*size),
(const void *)(cbase+(elem1+1)*size)) > 0)
{
sorted = 0;
break;
}
}
if (sorted)
return;
/* not sorted yet, generate a random permutation */
for (elem1=0; elem1<nmemb; elem1++)
{
elem2 = rand() / (RAND_MAX / nmemb + 1);
/* swap elem1 and elem2 bytewise */
for (count=0; count<size; count++)
{
temp = cbase[elem1*size + count];
cbase[elem1*size + count] = cbase[elem2*size + count];
cbase[elem2*size + count] = temp;
}
}
}
}
#ifdef TEST
#include <stdio.h>
int intcmp(const void *a, const void *b)
{
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y);
}
int main(void)
{
char buf[10];
int *array;
int n, count;
puts("BogoSort(tm) demonstration\n");
do
{
printf("How many elements to sort ? ");
fflush(stdout);
}
while (fgets(buf, sizeof buf, stdin)==NULL
|| sscanf(buf, "%d", &n)!=1
|| n<0);
array = malloc(sizeof *array * n);
if (array==NULL)
{
printf("Out of memory.");
return EXIT_FAILURE;
}
puts("Enter data to be sorted:");
for (count=0; count<n; count++)
{
do
{
printf("Enter value for element number %5d: ", count);
fflush(stdout);
}
while (fgets(buf, sizeof buf, stdin)==NULL
|| sscanf(buf, "%d", &array[count])!=1);
}
printf("Sorting...\n");
bsort(array, n, sizeof *array, intcmp);
printf("Results:\n");
for (count=0; count<n; count++)
printf("Element number %5d: %5d\n", count, array[count]);
return EXIT_SUCCESS;
}
#endif
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.