Stupid-sort -- an O(n*n!) sort program

[Donn Seeley]

Here is some C code that I wrote to implement the stupid sort program
discussed in this month's Programming Pearls column in the CACM (7/84,
p. 634).  No one came forth to claim credit for originating the
algorithm, but I suspect some people at Bell suggested it.

The algorithm is painfully simple -- to sort a list of values, permute
the list randomly and test the new list.  My own version has some
innovations: it uses linked list data structures (enabling the program
to trundle off into the forest of pointers every time it wants to
retrieve a value) and is non-deterministic, using the 4.2 BSD random()
function seeded with the current time.  One advantage of the algorithm
which was pointed out in the column and attributed to Doug McIlroy, is
that since the random number generator has a finite period, there will
be lists of items for which the algorithm will never generate the
sorted pattern; in other words the worst case time is O(infinity).  [I
should note here that stupider programs with best case time equal to
the worst case time are possible, but are inherently uninteresting.]
Due to the inefficency of the algorithm, the worst case time can be
reached with relatively small lists, on the order of 15...  Don't sort
your password file with stupid-sort unless you are a Time Lord.

Here is the code, formatted in a way that PROVES C is a dangerous
language:

------------------------------------------------------------------------
# include	<stdio.h>
struct stupid{struct stupid*s_next;char s_buf[BUFSIZ];};main(
argc,argv)int argc;char**argv;{struct stupid*s,*s2,*bs,*bs2,
*as,*as2;struct stupid*last_stupid=NULL,*first_stupid;int
count_stupids=0,n_stupid,i,j,wrong;int random(),srandom();
while(argc>1){++argv,--argc;if(**argv!='-')fprintf(
stderr,"stupid: %s: no file arguments\n",*argv);else fprintf(
stderr,"stupid: %s: no options either\n",*argv);}do{s=(struct
stupid*)calloc(1,sizeof(struct stupid));if(last_stupid)
last_stupid->s_next=s;else first_stupid=s;last_stupid=s;
++count_stupids;}while(gets(s->s_buf));--count_stupids;
srandom(time(0));do{for(i=0;i<count_stupids;++i){for
(s=first_stupid,j=0;j<i;s=s->s_next,++j);/*Ideally we
would loop on random() until the value fell into the range
0-(count_stupids-1), but I cheated*/n_stupid=random()%count_stupids;
for(s2=first_stupid,j=0;j<n_stupid;s2=s2->s_next,++j);
for(bs=first_stupid;bs->s_next&&bs->s_next!=s;bs=bs->s_next
);if(bs->s_next==NULL)bs=NULL;for(bs2=first_stupid;
bs2->s_next&&bs2->s_next!=s2;bs2=bs2->s_next);if(bs2->s_next
==NULL)bs2=NULL;for(as=first_stupid;as->s_next&&as!=
s->s_next;as=as->s_next);for(as2=first_stupid;as2->s_next&&
as2!=s2->s_next;as2=as2->s_next);if(s->s_next==s2){if(
bs)bs->s_next=s2;else first_stupid=s2;s2->s_next=s;s->s_next
=as2;}else if(s2->s_next==s){if(bs2)bs2->s_next=s;else
first_stupid=s;s->s_next=s2;s2->s_next=as;}else{if(bs)
bs->s_next=s2;else first_stupid=s2;if(bs2)bs2->s_next=s;
else first_stupid=s;s->s_next=as2;s2->s_next=as;}}wrong=0;
for(s=first_stupid;s->s_next&&s->s_next->s_next;s=s->s_next)
if(strcmp(s->s_buf,s->s_next->s_buf)>=0)wrong=1;}while(
wrong);for(s=first_stupid;s->s_next;s=s->s_next)puts(
s->s_buf);exit(-1);}
------------------------------------------------------------------------

Enjoy,

Donn Seeley    University of Utah CS Dept    donn at utah-cs.arpa
40 46' 6"N 111 50' 34"W    (801) 581-5668    decvax!utah-cs!donn