U23405@UICVM (Michael J. Steiner) (08/16/88)
I have heard of many types of sorting alorithms (such as insertion,
merge, selection, shell, and quick) (I'm not even mentioning bubble sort
:-).
I already have the algorithms for insertion sort and selecton sort. Could
anyone send me the algorthms, explanations of them, where to find the
algorithms, or where to find explanations of them? (I am also interested
in statistics about these sorting alorithms, such as which sort is
efficient for which kind of data, etc.)
I would appreciate it if you could send the algorithms coded in C (if you
decide to send the actual algorithms instead of a pointer :-) to them).
Also, does anyone have any informaion about mergesort?
Michael Steiner
Email: U23405@UICVMward@eplrx7.UUCP (Rick Ward) (08/18/88)
[request for sorting algorithms, preferably in C :-) ]
Michael,
I hope you are not a computer science student. Any self respecting
computer scientist would know where to look for these algorithms.
Try D.E. Knuth's The Art of Computer Programming Vol. 3 "Sorting and Searching"
or any of the other standard computer algorithm texts. Also, most books on C
include at least one sorting algorithm in them(commonly merge sort or
quicksort).
Rick
--
Rick Ward | E.I. Dupont Co.
uunet!eplrx7!ward | Engineering Physics Lab
(302) 695-7395 | Wilmington, Delaware 19898
| Mail Stop: E357-302davidsen@steinmetz.ge.com (William E. Davidsen Jr) (08/18/88)
I have a C program which will allow generation of data initialized in a
number of configurations, allows vector length to be set, and sorts with
any of 11 algorithms giving the CPU time. It optionally will give the
number of compares and moves.
One of the best places to get sorting info is Knuth, _Art of Computer
Programming_ vol 3 (Sorting and Searching). There is a discussion of
many of the common algorithms, including merge.
If you really want to see the program I can mail it. I have no
documentation, and was using it just to investigate why some sorts work
better than others.
--
bill davidsen (wedu@ge-crd.arpa)
{uunet | philabs | seismo}!steinmetz!crdos1!davidsen
"Stupidity, like virtue, is its own reward" -meroetzhei@sdsu.UUCP (William Roetzheim) (08/19/88)
In article <8808171405.AA05232@ucbvax.Berkeley.EDU> U23405@UICVM (Michael J. Steiner) writes: >I already have the algorithms for insertion sort and selecton sort. Could >anyone send me the algorthms, explanations of them, where to find the >algorithms, or where to find explanations of them? (I am also interested Sedgwick's (sp?) "Algorithms" has a good treatment of many sort algorithms, including merge sort. The algorithms are in Pacal and include good advice about when they are appropriate. The book "Numerical Recipies" also has many good sort algorithms. My version gives examples in fortran (which is a pain to convert to C because of different indexing of arrays), but there is now a version out with examples in C (I have it on order). WHR
bph@buengc.BU.EDU (Blair P. Houghton) (08/19/88)
In article <643@eplrx7.UUCP> ward@eplrx7.UUCP (Rick Ward) writes: >[request for sorting algorithms, preferably in C :-) ] > >Michael, > I hope you are not a computer science student. Any self respecting >computer scientist would know where to look for these algorithms. Raw-ther, we'd say "I wrote one of those when I was eleven on my AIM-1; got a minute? Here's how it goes..." :-) 8-) 8^) ,, oo (evolution of Smiley Erectus) > \/ >Try D.E. Knuth's The Art of Computer Programming Vol. 3 "Sorting and Searching" Concur heartily. Whether yer a computer scientist or not, this is the book to read; I think I'm going to go look at my copy now. I'm in need of a little fundamentalism. --Blair
usenet@dandelion.CI.COM (News Administrator) (08/20/88)
For a discussion of and references to 37 different sorting algorithms, see: From: jim@blossom.ci.com (Jim Hurt) Path: blossom!jim W.A. Martin, "Sorting", _ACM Computing Surveys_, Volume 3, Number 4, December 1971, pp 147-174. Jim Hurt
dharvey@wsccs.UUCP (David Harvey) (08/31/88)
> Michael, > I hope you are not a computer science student. Any self respecting > computer scientist would know where to look for these algorithms. > > Try D.E. Knuth's The Art of Computer Programming Vol. 3 "Sorting and Searching" > or any of the other standard computer algorithm texts. Also, most books on C > include at least one sorting algorithm in them(commonly merge sort or > quicksort). > Amen! There are so many books out there with sorting algorithms it seems that a posting to the net like this deserves to be flamed. As for a self respecting computer scientist they don't even look at the text.... they just write it! dharvey@wsccs disclaimer: I am responsible for Nobody and Nobody is responsible for me. (-:
gwyn@smoke.BRL.MIL (Doug Gwyn) (11/09/89)
In article <2835@phred.UUCP> stevel@phred.UUCP (Steve Leach) writes: >Sorry if this has been discussed befor, but how are the following >sorting methods different? The standard answer to such questions about sorting techniques is: Read Donald Knuth's "The Art of Computer Programming, Vol. 3 -- Sorting and Searching".
bradb@cs.toronto.edu (Brad Brown) (11/10/89)
gwyn@smoke.BRL.MIL (Doug Gwyn) writes: >In article <2835@phred.UUCP> stevel@phred.UUCP (Steve Leach) writes: >>Sorry if this has been discussed befor, but how are the following >>sorting methods different? >The standard answer to such questions about sorting techniques is: >Read Donald Knuth's "The Art of Computer Programming, Vol. 3 -- >Sorting and Searching". A more accessable work is Sedgwick's "Algorithms, 2nd ed.". Knuth is great if you want to know just about everything there is to know about an algorithm, but the analysis can get a bit thick and the source code is hard to read sometimes. Sedgwick's book is less rigerous, but the source is in Pascal and the style is much more conversational. When you start to look at the differences between the algorithms, look especially at the complexity (roughly the worst case time it will take to run), the mean complexity, the performance on partially sorted data (some sorts, like quicksort, can degenerate badly if you give it partially sorted data), whether you can sort in-place or on disk, whether you can sort a linked list or an array... (-: Brad Brown :-) bradb@ai.utoronto.ca
peter@ficc.uu.net (Peter da Silva) (11/11/89)
I like Horowitz and Sahni, "Fundamentals of Computer Algorithms". They're a lot more readable than Knuth, and use a high-level pseudocode for everything. (whatever posessed Knuth to express algorithms in assembly?) Horowitz & Sahni, Fundamentals of Computer Algorithms. Computer Science Press Inc. 11 Taft Court Rockville, MD 20850 ISBN 0-914894-22-6 There's an earlier companion book, "Fundamentals of Data Structures". -- `-_-' Peter da Silva <peter@ficc.uu.net> <peter@sugar.hackercorp.com>. 'U` -------------- +1 713 274 5180. "*Real* wizards don't whine about how they paid their dues" -- Quentin Johnson quent@atanasoff.cs.iastate.edu
oz@yunexus.UUCP (Ozan Yigit) (11/13/89)
In article <11564@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes: >The standard answer to such questions about sorting techniques is: >Read Donald Knuth's "The Art of Computer Programming, Vol. 3 -- >Sorting and Searching". On the other hand, if you do not feel like beeping around with Knuth's little problems and games using MIX, try "Handbook of Algorithms and Data Structures" by Gaston H. Gonnet, Addison-Wesley. oz -- There are two kinds of fool. Internet: oz@nexus.yorku.ca One says, "This is old, and therefore good" Uucp: uunet!utai!yunexus!oz And one says "This is new, and therefore Better" Bitnet: oz@[yulibra|yuyetti] John Brunner (The Shockwave Rider) Phonet: +1 416 736-5257x3976
jeffrey@algor2.algorists.com (Jeffrey Kegler) (11/18/89)
In article <6916@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: >I like Horowitz and Sahni, "Fundamentals of Computer Algorithms". They're >a lot more readable than Knuth, and use a high-level pseudocode for >everything. (whatever posessed Knuth to express algorithms in assembly?) It is important to remember that Knuth's sorting book is over 15 years old in a field that moves very quickly. In particular, the decision to use assembly, while by current standards, very ill-advised, looked better then. C use was not then widespead (the UNIX kernel had just been rewritten in C from assembler), so what was Knuth to do? Use FORTRAN? ALGOL? Either probably would have been better, actually, than MIX, but at least you can see that Knuth's choice was a rational one at the time. The "standard" answer to algorithms questions is "read Knuth" (a variant of RTFM), but I feel this is more of a dismissal than an answer. Knuth is far more often cited or used as a status symbol then read. You need not have been around this business as long as I have to have seen Knuth's volumes behind the desks of many a poor excuse for a programmer. Knuth is still an important source, but is no longer up to date and was always hard to read. I often wonder if his problems do more to scare readers off than increase their understanding of the field. Knuth should not be anyone's first book on algorithms. Learning algorithms from Knuth is almost as bad as learning physics from Newton in the Latin original. -- Jeffrey Kegler, Independent UNIX Consultant, Algorists, Inc. jeffrey@algor2.ALGORISTS.COM or uunet!algor2!jeffrey 1762 Wainwright DR, Reston VA 22090
amull@Morgan.COM (Andrew P. Mullhaupt) (11/20/89)
In article <1989Nov17.185514.15726@algor2.algorists.com>, jeffrey@algor2.algorists.com (Jeffrey Kegler) writes: > In article <6916@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: > >I like Horowitz and Sahni, "Fundamentals of Computer Algorithms". They're > >a lot more readable than Knuth, and use a high-level pseudocode for > >everything. (whatever posessed Knuth to express algorithms in assembly?) > > It is important to remember that Knuth's sorting book is over 15 years > old in a field that moves very quickly. In particular, the decision > to use assembly, while by current standards, very ill-advised, looked > better then. C use was not then widespead (the UNIX kernel had just > been rewritten in C from assembler), so what was Knuth to do? Use > FORTRAN? ALGOL? Either probably would have been better, actually, > than MIX, but at least you can see that Knuth's choice was a rational > one at the time. It would be wishful thinking to expect that had Knuth chosen ALGOL, the state of computer science would be better, but that was the acceptable choice at the time. The pseudocode in the literature at the time, and to a great extent still today, is much more ALGOL-like than C is. Your preferred choice (Horowitz and Sahni) is quite good, but an order of magnitude less comprehensive than Knuth. Your preference is a bit odd since SPARKS, the pseudocode of Horowitz and Sahni, is FORTRAN based, in fact they actually used a FORTRAN preprocessor for some courses taught out of their books. As for using C in such a book, well I think this would be tragic. Just as C programmers like to deprecate Pascal as a teaching toy, the C language is wide open to charges of unsuitability as a teaching tool. Let's admit it; C is about as silly as a first computer language can be if you want to teach anything at a college level. You have to treat bizarre style issues in C like when to use for or while, and how to keep the students from running wild with the side-effect operators to compact their code onto one line. Here at Morgan Stanley, we often hire people who don't program but who have expertise in science, engineering or finance. We teach them APL as a first language, because it's what we use. When you have to read code in a poorly structured language written by people who are not likely to become concerned with style, correctness, and maintainability you have to deal with a lot of bugs and hassles I suspect wouldn't appear in a better structured language. I shudder to think if we didn't hire a professional staff for our C programming, (which we do, and they are excellent, BTW) but this has to be seen as a limit on the accessibility and readability of C, similar to that (if not even worse than that of APL). Later, Andrew Mullhaupt Disclaimer: Any opinions expressed above are not necessarily those of Morgan Stanley and Co., Inc.
kurtl@fai.UUCP (Kurt Luoto) (11/23/89)
In article <1989Nov17.185514.15726@algor2.algorists.com> jeffrey@algor2.ALGORISTS.COM (Jeffrey Kegler) writes: >In article <6916@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: >>I like Horowitz and Sahni, "Fundamentals of Computer Algorithms". They're >>a lot more readable than Knuth, and use a high-level pseudocode for >>everything. (whatever posessed Knuth to express algorithms in assembly?) > >It is important to remember that Knuth's sorting book is over 15 years >old in a field that moves very quickly. In particular, the decision >to use assembly, while by current standards, very ill-advised, looked >better then. C use was not then widespead (the UNIX kernel had just >been rewritten in C from assembler), so what was Knuth to do? Use >FORTRAN? ALGOL? Either probably would have been better, actually, >than MIX, but at least you can see that Knuth's choice was a rational >one at the time. I won't pretend to be expert enough to speak for Knuth, but there are some reasons for using a (pseudo-)assembly language. (I might have read these from an interview with Knuth, but don't take my word for it.) Mr. Kegler points out one good reason. Another reason is that it is good for students of computing to have a feel for what goes on inside of a computer, even if they are going to be programming in a high-level language. It is much easier to explain the costs of various algorithms when you have a concrete model to compare with. With the MIX model, you can "run" your algorithm, count execution cycles or storage requirements, and actually *see* the costs/behaviour for various cases. In a high level language it is somewhat harder to get a feel for these things. For example, not all statements in C or Pascal have the same cost, These may not be compelling reasons, but they are rational. >The "standard" answer to algorithms questions is "read Knuth" (a >variant of RTFM), but I feel this is more of a dismissal than an >answer. Knuth is far more often cited or used as a status symbol then >read. You need not have been around this business as long as I have >to have seen Knuth's volumes behind the desks of many a poor excuse >for a programmer. Knuth is still an important source, but is no >longer up to date and was always hard to read. I often wonder if his >problems do more to scare readers off than increase their >understanding of the field. It is true that some will find Knuth's style somewhat inaccessible. First, I think this is because he is a mathematician by training and is targeting a math-literate audience. In fact, a large chunk of his first volume seems devoted to simply providing the mathematical tools necessary for the later volumes, where much of the material of interest to programmers is found. Second, it seems to me that he is writing more for theorists, those whose field is the mathematics of computation (I *hate* the term "computer science"!) as opposed to writing a reference for programmers who "just want the algorithms" (cookbook procedures) without the theoretical derivations. Its sort of like a calculus text written for math majors, which includes all the proofs, as opposed to a calculus text written for engineers or soft-sciences which gives the statement of the theorems and the formulas, but leaves out the proofs. Third, Knuth crams *a lot* of material into his volumes. If you have worked through all of his exercises (I have not), you have learned much indeed. But for practical every-day use, you usually only need a fraction of the information. Other texts will lead you more quickly to this fraction. > >Knuth should not be anyone's first book on algorithms. Learning >algorithms from Knuth is almost as bad as learning physics from Newton >in the Latin original. I agree that there are better introductory texts. But if you have the time and motivation, I cannot see how learning from Knuth can in any way be "bad". We could use more programmers with good mathematical training. >-- > >Jeffrey Kegler, Independent UNIX Consultant, Algorists, Inc. >jeffrey@algor2.ALGORISTS.COM or uunet!algor2!jeffrey >1762 Wainwright DR, Reston VA 22090 -- ---------------- Kurt W. Luoto kurtl@fai.com or ...!sun!fai!kurtl