Article View: comp.std.c
Article #950qsort
From: Luiz H de Figueiredo
Date: Sat, 18 Nov 1989 18:58
Date: Sat, 18 Nov 1989 18:58
20 lines
1256 bytes
1256 bytes
In a recent thread about sorting strings, someone suggested that qsort was not the way to go because quicksort is not very good for nearly ordered files. My question is: Does qsort have to implement quicksort? My point is that the *name* qsort is historical but qsort can actually be very smart, eg. switching to insertion for small segments and/or pre-scan the file (array) to avoid quadratic behaviour for sorted data. In other words, qsort does not even have to implement quicksort at all! What is more useful to assume is that qsort is *very* efficient, so that we don't have to re-invent the wheel every day. What does the standard say about this? Luiz Henrique de Figueiredo internet: lhf@aries5.uwaterloo.ca Computer Systems Group bitnet: lhf@watcsg.bitnet University of Waterloo Waterloo, Ontario, Canada N2L 3G1
Technical Details
Message-ID:
<861@maytag.waterloo.edu>Path:
arc1-ca.pugleaf.net!utzoo!mnetor!tmsoft!torsqnt!jarvis.csri.toronto.edu!rutgers!att!watmath!maytag!aries5!lhfShow Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!mnetor!tmsoft!torsqnt!jarvis.csri.toronto.edu!rutgers!att!watmath!maytag!aries5!lhf From: lhf@aries5 (Luiz H de Figueiredo) Newsgroups: comp.std.c Subject: qsort Message-ID: <861@maytag.waterloo.edu> Date: 18 Nov 89 18:58:55 GMT Sender: daemon@maytag.waterloo.edu Reply-To: lhf@aries5 (Luiz H de Figueiredo) Organization: Computer Systems Group, University of Waterloo Lines: 20