donn@utah-cs.UUCP (Donn Seeley) (07/14/84)
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@utah-cs.arpa
40 46' 6"N 111 50' 34"W (801) 581-5668 decvax!utah-cs!donndan@rna.UUCP (Dan Ts'o) (07/19/84)
Hi, I don't think your formatted C stupid-sort program "PROVES" that C is a dangerous language. If you run your text through the C beautifier, the output is quite reasonable. cheers, Dan
johan@apple.UUCP (07/20/84)
I am currently trying to sort 15 numbers using the stupid sort
algorithm, this is the current progress (using a VAX 750)
PID TT STAT TIME COMMAND
6981 10 R N 4064:53 worstsort
The code was compiled with the optimizer. We have very little load
on our machine at the time so I will let it run while I go to SIGGraph
for a week. I will let you know how long time it took...
_________________________Computare necesse est!______________________
Johan Strandberg
Apple Computer Education Research Group [ERG]
{mtxinu,dual,nsc,voder}!apple!johansrlm@ukc.UUCP (S.R.L.Meira) (07/24/84)
it is a lot easier to understand what is going on,
and by the way more efficient (!) although still terrible,
if you choose the right sort of language. look at the
same thing in krc (kent recursive calculator), a purely
applicative, non-strict, higher order language we use
over here:
ordered [] = true
ordered [a] = true
ordered (a:b:x) = a <= b & ordered (b:x)
perms [] = [[]]
perms x = { a:y | a <- x ; y <- perms (x -- [a]) }
perm_sort x = head (filter ordered (perms x))
i think it is all self-explanatory (of course). for details,
mail me in the address below.
*********************************************
silvio lemos meira
UUCP: ...!{vax135,mcvax}!ukc!srlm
ARPA: srlm%eagle@ucl-cs
Post:
computing laboratory
university of kent at canterbury
canterbury ct2 7nf uk
Phone:
+44 227 66822 extension 568
*********************************************johan@apple.UUCP (Johan Strandberg) (07/29/84)
> I am currently trying to sort 15 numbers using the stupid sort > algorithm, this is the current progress (using a VAX 750) > > PID TT STAT TIME COMMAND > 6981 10 R N 4064:53 worstsort > > The code was compiled with the optimizer. We have very little load > on our machine at the time so I will let it run while I go to SIGGraph > for a week. I will let you know how long time it took... YES! I let the stupid sort run all thru SIGGraph... and this is the "result" (or absense thereof). I will now kill this before it actually completes and therebye does something usefull. PID TT STAT TIME COMMAND 6981 10 R N 16154:43 worstsort 16154 minutes = 269.23 hours = 11.22 days = 0.000307134 centuries = 0.307134 mC _________________________Computare necesse est!______________________ Johan Strandberg Apple Computer Education Research Group [ERG] {mtxinu,dual,nsc,voder}!apple!johan