What are some practical uses of Quicksort

9. Quicksort

C.A.R. Hoare developed; since then it has been studied by many researchers. Quicksort is popular because it is not difficult to implement, because it is a good "general purpose" sorting method (it works well in many different situations), and because in many situations it requires fewer resources than any other sorting method.

The advantages of the Quicksort algorithm are that it runs "in-place" (it only uses a small auxiliary stack) for sorting N Elements on average only approximately N log N Requires operations and has an extremely short inner loop. The disadvantages of the algorithm are that it is recursive (implementation is complicated if recursion is not available) and, in the worst case, it is roughly N2 Operations and that it is prone to failure: A simple mistake in the implementation can go unnoticed and lead to the fact that the algorithm works poorly for some files.

The power of Quicksort has been very well researched. Quicksort was the subject of a thorough mathematical analysis, so that very precise statements can be made about questions of performance. This analysis has been corroborated by extensive empirical experience and the algorithm has been refined to the point where it has become the preferred method for a wide range of practical sorting applications. For this reason it is worthwhile for us to look a little more carefully than with other algorithms ways of an efficient implementation of Quicksort. Similar implementation techniques are also suitable for other algorithms; at Quicksort we can use it without hesitation because its performance has been so well researched.

It is a great temptation to want to improve Quicksort, as ever faster sorting algorithms are one of the greatest challenges in computer science. Shortly after Hoare first published the algorithm, "improved" variants appeared in the literature. Many ideas were tried and analyzed, but most of the time it led to disappointment. The algorithm is already balanced enough that the effects of improvements in one part of the program can be more than offset by the effects of decreased performance in another part of the program. However, we will examine in more detail three modifications that greatly improve Quicksort.

A carefully adapted variant of Quicksort will certainly run much faster on most computers than any other sorting method. It should be noted, however, that any algorithm can be made more sensitive by adapting it, and undesirable and unexpected effects can occur for some input data. If a variant has been developed which appears to be free of such effects, it should be the program which is to be used as a library standard sorting program or for a serious sorting application. However, if you do not want to invest the effort - to be sure that an implementation of Quicksort is not faulty - Shellsort is definitely a safer alternative, which runs quite efficiently with less effort for the implementation.