quan@sol.surv.utas.edu.au (Stephen Quan) (03/24/91)
I am in desperate seek of ideas on how to implement "QuickSort" or other optimin sorting algorithm without the use of recursion, our Sun Fortran (F77 version 1.2 on SunOS 4.0) compiler doesn't support recursion very well. At the moment I'm using a bubble sort and it is inadequate with the data I am working with. (A file/table of 80000 integer pairs). Stephen Quan, quan@sol.surv.utas.edu.au, University of Tasmania, Surveying Dept., Australia.
ralph@uhheph.phys.hawaii.edu (Ralph Becker-Szendy) (03/24/91)
In article <quan.669809324@sol> quan@sol.surv.utas.edu.au (Stephen Quan) writes: >I am in desperate seek of ideas on how to implement "QuickSort" or other >optimin sorting algorithm without the use of recursion, our Sun Fortran >(F77 version 1.2 on SunOS 4.0) compiler doesn't support recursion very >well. > >At the moment I'm using a bubble sort and it is inadequate with the data >I am working with. (A file/table of 80000 integer pairs). > >Stephen Quan, >quan@sol.surv.utas.edu.au, >University of Tasmania, >Surveying Dept., >Australia. Questions like this prove that "the book" has to be read by more people. Here is the answer: Numerical Recipes, by Press/Flannery/Teukolsky/Vetterling, Cambridge Univ Press. Comes with FORTRAN example programs. A reasonably good sorting routine is among them, you can just type it in (there is also an example disk in MS-DOS format one can cuy with the book), for people too lazy to type the examples in. Page 235 has a pretty short quicksort program. Not the world's greates sorting routine, but good enough for most problems. The same program in PASCAL is in an appendix, and a version of the book in C is available too. As another reader of this group pointed out a while ago (in no uncertain words), "the book" is not the state of the art. It is not even the greatest textbook of numerical mathematics. But it contains lots of handy example programs (which work more or less, they are examples after all), and it explains the principles of numerical work. I think it is a very good book WITH LIMITATIONS. -- Ralph Becker-Szendy UHHEPG=24742::RALPH (HEPNet,SPAN) University of Hawaii RALPH@UHHEPG.PHYS.HAWAII.EDU High Energy Physics Group RALPH@UHHEPG.BITNET Watanabe Hall #203, 2505 Correa Road, Honolulu, HI 96822 (808)956-2931
gbastin@x102c.harris-atd.com (Gary Bastin 60293) (03/26/91)
In article <12120@uhccux.uhcc.Hawaii.Edu> ralph@uhheph.phys.hawaii.edu (Ralph Becker-Szendy) writes: > >Questions like this prove that "the book" has to be read by more people. Here >is the answer: Numerical Recipes, by Press/Flannery/Teukolsky/Vetterling, >Cambridge Univ Press. Comes with FORTRAN example programs. A reasonably good >sorting routine is among them... >The same program in PASCAL is in an appendix, and a version of the book in >C is available too. I should point out that in the latest FORTRAN version, the PASCAL appendix has been dropped. There is now a separate PASCAL version of the book. From what I understand, the original PASCAL appendix was essentially a straight translation from FORTRAN to PASCAL. The newer PASCAL version utilizes pointers and other features possible in PASCAL which the original FORTRAN appendix version did not include. The new FORTRAN version, according to the intro, represents the current state of the code, and does not include a list of changes from earlier FORTRAN editions. Can anyone comment on the current code's capability versus current standard practice. I am specifically wondering if some of the criticism I have read here on the net is more directed at earlier versions than at the current version. Thanks in advance! Gary Bastin, WB4YAF /-/-/ Internet: gbastin@x102c.ess.harris.com Mail Stop 102-4826 | phone: (407) 729-3045 Harris Corporation GASD | P.O.B. 94000, Melbourne FL 32902 Speaking from, but not for, Harris!
corrigan@weber.ucsd.edu (Michael J. Corrigan) (03/27/91)
In article <quan.669809324@sol> quan@sol.surv.utas.edu.au (Stephen Quan) writes: }I am in desperate seek of ideas on how to implement "QuickSort" or other }optimin sorting algorithm without the use of recursion, our Sun Fortran }(F77 version 1.2 on SunOS 4.0) compiler doesn't support recursion very }well. You don't have to *implement* such an algorithm. You can call the system-supplied C function qsort and link it in using f77 on a SUN system, I would suspect. Quite a number of the system-supplied C functions are also supplied in fortran equivalents on UNIX systems. Try "man 3f qsort" to see if the fortran library has this call. You can also do it the harder way and link the actual C call in. I wrote up a sample fortran program that sorts an 80000x2 array in around 30 seconds. I don't know if that is fast or slow, but at least you don't have to buy a book and type it in. E-mail me for the sample fortran program and C wrapper code. Michael J. Corrigan corrigan@ucsd.edu