Xref: utzoo comp.sources.wanted:7423 alt.msdos.programmer:45
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!unmvax!pprg.unm.edu!hc!lanl!opus!yorick
From: yorick@nmsu.edu (Yorick Wilks)
Newsgroups: comp.sources.wanted,alt.msdos.programmer
Subject: Re: Need algorithm to scramble order of array
Message-ID: <YORICK.89May17141021@kythera.nmsu.edu>
Date: 17 May 89 20:10:21 GMT
References: <3008@cps3xx.UUCP> <LOTTO.89May17112504@midas.harvard.edu>
Sender: news@nmsu.edu
Followup-To: comp.sources.wanted
Organization: NMSU Computer Science
Lines: 29
In-reply-to: lotto@midas.harvard.edu's message of 17 May 89 15:25:04 GMT


In article <LOTTO.89May17112504@midas.harvard.edu> lotto@midas.harvard.edu (Gerald I. Lotto) writes:

   One method that I like to use is to turn the array into 2 by n matrix.
   Fill array[n][2] with random numbers between 1 and m (m >> n), and
   sort "rows" by the "second column".

i wasn't going to worry about this much until this bogus method
appeared on the net.   this method suffers from a bias toward original
sort (modulo the stability of the sorting algorithm).  the bias is
small if m/n is large, but is always there.

much better is to use the following algorithm which is adapted from knuth:

/* shuffle the contents of an array... integers here, but they really
   could be anything */
shuffle(arr,n)
int arr[];
int n;
{
  /* walk along, inserting each element in a random place */
  for (i=1;i<n;i++) {
    swap(arr[i],arr[random()%(i+1)]);
  }
}


of course it is difficult to do this in parallel, or in a single apl
line, but at least it produces the correct result.