home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / lisp / 3156 < prev    next >
Encoding:
Text File  |  1992-12-30  |  2.1 KB  |  57 lines
  1. Newsgroups: comp.lang.lisp
  2. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!news.acns.nwu.edu!news.ils.nwu.edu!anaxagoras!krulwich
  3. From: krulwich@zowie.ils.nwu.edu (Bruce Krulwich)
  4. Subject: Re: sorting arrays
  5. In-Reply-To: lewocz@acsu.buffalo.edu's message of 30 Dec 92 00:00:11 GMT
  6. Message-ID: <KRULWICH.92Dec30130915@zowie.ils.nwu.edu>
  7. Sender: usenet@ils.nwu.edu (Mr. usenet)
  8. Nntp-Posting-Host: zowie.ils.nwu.edu
  9. Organization: The Institute for the Learning Sciences, Evanston, IL
  10. References: <C01pCC.MFK@acsu.buffalo.edu>
  11. Date: Wed, 30 Dec 1992 19:09:15 GMT
  12. Lines: 43
  13.  
  14.  
  15. lewocz@acsu.buffalo.edu (John S. Lewocz) writes:
  16.  
  17. > What would be the most effiecient way to sort a two-dimensional
  18. > array using an arbitrary column as a key?
  19.  
  20. I think that the following solution is pretty efficient, since it doesn't
  21. require copying row data during the sort, or creating loads of new arrays.
  22.  
  23. It works by sorting a seperate vector that contains numbers of rows of the
  24. original array.  This way the SORT function just sorts an integer vector,
  25. which should be pretty quick, using a KEY that maps onto the array being
  26. sorted.  Then we just copy the data into the appropriate rows of a new array.
  27. Consing is limited to making one vector the side of the row-dimension of the
  28. original array, and then making a new array to return.  
  29.  
  30. ** Note that this is _not_ a destructive sort (unlike CLtL SORT), but it
  31. shouldn't be that hard to do the final copying into itself instead of into a
  32. new array.
  33.  
  34. (defun sort-array-by-col (a c &optional (p #'<))
  35.   "Sort rows of 2-dimensional array A by value of column C using predicate P"
  36.   (let* ((num-rows (car (array-dimensions a)))
  37.      (index-vec (do ((v (make-array num-rows))
  38.              (i 0 (1+ i)))
  39.             ((= i num-rows) v)
  40.               (setf (elt v i) i)))
  41.      (sorted-index (sort index-vec p :key #'(lambda (r) (aref a r c))))
  42.      (new-array (make-array (array-dimensions a)))
  43.      )
  44.     (dotimes (r (car (array-dimensions a)))
  45.       (dotimes (c (cadr (array-dimensions a)))
  46.     (setf (aref new-array r c)
  47.           (aref a (elt sorted-index r) c))))
  48.     new-array))
  49.      
  50.  
  51. Enjoy!
  52.  
  53. Bruce Krulwich
  54. krulwich@ils.nwu.edu
  55.  
  56.  
  57.