qsort() Appears Extremely Slow in Worst-Case Situations |
Q48965
5.00 5.10 6.00 6.00a 6.00ax 7.00 | 5.10 6.00 6.00a | 1.00 1.50 MS-DOS | OS/2 | WINDOWS kbprg ---------------------------------------------------------------------- The information in this article applies to: - The C Run-time (CRT), included with: - Microsoft C for MS-DOS, versions 5.0, 5.1, 6.0, 6.0a, and 6.0ax - Microsoft C for OS/2, versions 5.1, 6.0, and 6.0a - Microsoft C/C++ for MS-DOS, version 7.0 - Microsoft Visual C++ for Windows, versions 1.0 and 1.5 ---------------------------------------------------------------------- SUMMARY ======= When using qsort() in a worst-case situation (for example, the array is already sorted in reverse order), the qsort() library routine appears to take an extremely long time. MORE INFORMATION ================ The qsort() routine provided by Microsoft was optimized for both speed and stack usage [stack space is important because qsort() is heavily recursive]. Therefore, in a worst-case situation, which could recurse up to the number of elements in the list, qsort() sacrifices speed for stack space. This behavior allows larger lists to be sorted without stack overflow problems. Furthermore, Microsoft's qsort() routine is very competitive in sorting random files, the type of array for which quick sorts are designed. If used judiciously, Microsoft's qsort() is a very effective sort routine. In worst-case situations, Microsoft's qsort() is slower than some other sorting routines, but successfully sorts larger arrays without stack overflow problems. Additional reference words: kbinf 1.00 1.50 6.00 6.00a 6.00ax 7.00 KBCategory: kbprg KBSubcategory: CRTIss
Keywords : kb16bitonly
Issue type :
Technology : kbVCsearch kbAudDeveloper kbCRT
Last Reviewed: May 5, 2001 |
