Hi! 9-Июл-2004 05:02 [EMAIL PROTECTED] (Eric Auer) wrote to [EMAIL PROTECTED]:
EA> Hi, I would like to add that: EA> http://www.wordiq.com/definition/Quicksort EA> Quicksort takes average O(n*log(n)) but worst O(n*n) comparisons, If you get medium item from fixed position, you always may encounter array with order, where QSORT is worser than bubble sort (worsest sorting algorithm). But: ______________O\_/_________________________________\_/O______________ Background The Quicker Sort algorithm was first described by C.A.R.Hoare in the Computer Journal, No. 5 (1962), pp.10..15, and in addition is frequently described in computing literature, notably in D. Knuth's Sorting and Searching. The method used here includes a number of refinements: - The median-of-three technique described by Singleton (Communications of the A.C.M., No 12 (1969) pp 185..187) is used, where the median operation is also the special case sort for 3 elements. This slightly improves the average speed, especially when comparisons are slower than exchanges, but more importantly it prevents worst-case behavior on partly sorted files. If a simplistic quicker-sort is run on a file which is only slightly disordered (a common need in some applications) then it is as slow as a bubble-sort. The median technique prevents this. Another serious problem with the plain algorithm is that worst-case behavior causes very deep recursion (almost one level per table element !), so again it is best to use the median technique. _____________________________________________________________________ O/~\ /~\O This is comment from qsort.cas from BC++ RTL. EA> and average O(log n) but worst O(n) stack (and no head)... _If_ you use recursion for both parts of splitted array, then in worsest case your stack depth will be N for all items in array. But if you recurse only for smaller part (and use loop for second part), then stack depth will not deeper than O(log2 N) (for 65536 items stack depth will not be more than 16). BC++ RTL qsort.asm uses loop for bigger part... EA> So I increased stack size of SORT to 16k, which means that it can EA> "sort" up to 700 (roughly) identical lines (worst case). EA> For sorting 10000 lines from RBIL, even a tiny 6k stack was enough. ...Thus, your "6k of stack" is too big for your SORT (unless you place on stack some big buffers). At least, this is true under BC++. ------------------------------------------------------- This SF.Net email sponsored by Black Hat Briefings & Training. Attend Black Hat Briefings & Training, Las Vegas July 24-29 - digital self defense, top technical experts, no vendor pitches, unmatched networking opportunities. Visit www.blackhat.com _______________________________________________ Freedos-devel mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/freedos-devel
