home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / sys / hp48 / 6277 < prev    next >
Encoding:
Internet Message Format  |  1992-12-12  |  1.5 KB
  1. From: akcs.joehorn@hpcvbbs.cv.hp.com (Joseph K. Horn)
  2. Date: Sat, 12 Dec 1992 11:40:02 GMT
  3. Subject: Insert into Sorted List
  4. Message-ID: <2b29cf68.2387comp.sys.hp48@hpcvbbs.cv.hp.com>
  5. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!europa.asd.contel.com!emory!swrinde!zaphod.mps.ohio-state.edu!sdd.hp.com!hp-cv!hp-pcd!hpcvra!rnews!hpcvbbs!akcs.joehorn
  6. Newsgroups: comp.sys.hp48
  7. Lines: 32
  8.  
  9. I challenged my students to write a program (in User RPL) that inserts
  10. a real number into a list of pre-sorted reals, in such a way that the
  11. list is still in order.  They all developed linear-search methods
  12. which work okay, but are slow.  The following "binary search" method
  13. is much faster.  Their fastest program took over 38 seconds to insert
  14. 888.8 into a list of the integers 1 through 1000; the program below
  15. takes less than two seconds.
  16.  
  17.                         Is there a better way?
  18.  
  19. %%HP: T(3)A(D)F(.);
  20. @ ORD3 by Joe Horn; inserts a real into a list in the right place.
  21. @ 2: List of pre-sorted reals; 1: real
  22. \<<
  23.   SWAP OBJ\-> DUP 2 + ROLL OVER 6 + 5
  24.     WHILE DUP2 - 1 >
  25.     REPEAT DUP2 + 2 / CEIL DUP PICK 5 PICK
  26.       IF >
  27.       THEN SWAP DROP
  28.       ELSE ROT DROP SWAP
  29.       END
  30.     END DROP 4 -
  31.   ROLLD 1 + \->LIST
  32. \>>
  33.  
  34. Example:  { 5 7 9 11 13 }  10  ORD3  -->  { 5 7 9 10 11 13 }
  35.  
  36. Note: Program must be able to handle the possibility of insertion at
  37. the ends of the list.  The program above also just happens to be able
  38. to handle the case of insertion into an empty list.
  39.  
  40. -Joe Horn-
  41.  
  42.