home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / lang / c / 13335 < prev    next >
Encoding:
Internet Message Format  |  1992-09-08  |  1.8 KB
  1. Path: sparky!uunet!news.claremont.edu!ucivax!news.service.uci.edu!beckman.com!dn66!a_rubin
  2. Newsgroups: comp.lang.c
  3. Subject: Re: bogosort revisited (with source)
  4. Message-ID: <a_rubin.715969133@dn66>
  5. From: a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
  6. Date: 8 Sep 92 16:18:53 GMT
  7. References: <Bu41Lu.IKB@news.cso.uiuc.edu> <1992Sep6.023647.1872@smds.com> 
  8.  <1992Sep6.111107.16924@grebyn.com> <1992Sep6.164314.14858@athena.mit.edu>
  9. Nntp-Posting-Host: dn66.dse.beckman.com
  10. Lines: 34
  11.  
  12. In <1992Sep6.164314.14858@athena.mit.edu> tada@athena.mit.edu (Michael J Zehr) writes:
  13.  
  14. >Okay, deterministic and horrible:
  15.  
  16. >Generate all sorted lists of length N of numbers drawn from the domain
  17. >of the elements you're sorting.*  (for example, all sorted lists of 2^32
  18. >bit patterns.)  (there are a lot of them, bounded by 2^32^N for this
  19. >example.)** Check to see if the list contains exactly the elements you're
  20. >trying to sort.  (Do this by some O(N^2) algorithm.)
  21.  
  22. >This is now O(n^2 * K^N) where K is the number of unique elements of the
  23. >data type that the sort will handle.  Furthermore, it's deterministic.
  24.  
  25. >-michael j zehr
  26.  
  27. >_______
  28. >* If you want, generate all sets instead of just the sorted one.  Then
  29. >you get horrible space as well as time characteristics!
  30.  
  31. >** I couldn't quickly come up with the closed form of this expression,
  32. >but I only had about ten minutes to spare.  Can someone else do better?
  33. >It looks really messy after N>3...
  34.  
  35.  /  2^32 \      (2^32) ! 
  36. |         | = ----------------
  37.  \   N   /    (2^32-N)! N!
  38.  
  39.  
  40. (Well, you asked.)
  41. --
  42. Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
  43. 216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
  44. My opinions are my own, and do not represent those of my employer.
  45. My interaction with our news system is unstable; please mail anything important.
  46.