Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.1 6/24/83; site utah-cs.UUCP Path: utzoo!linus!decvax!harpo!utah-cs!donn From: donn@utah-cs.UUCP (Donn Seeley) Newsgroups: net.sources,net.lang.c Subject: Stupid-sort -- an O(n*n!) sort program Message-ID: <2897@utah-cs.UUCP> Date: Fri, 13-Jul-84 20:07:47 EDT Article-I.D.: utah-cs.2897 Posted: Fri Jul 13 20:07:47 1984 Date-Received: Sun, 15-Jul-84 10:18:50 EDT Organization: CS Dept., University of Utah Lines: 62 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 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;is_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;js_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!donn