endr : (*now and delimit the left partition*until > until end nonrecursivequicksort analysis of quicksort in order to analyze the performance of quicksortwe need to investigate the behavior of the partitioning process first after having selected bound xit sweeps the entire array henceexactly comparisons are performed the number of exchanges can be determind by the following probabilistic argument with fixed bound uthe expected number of exchange operations is equal to the number of elements in the left part of the partitionnamely umultiplied by the probability that such an element reached its place by an exchange an exchange had taken place if the element had previously been part of the right partitionthe probablity for this is ( - )/ the expected number of exchanges is therefore the average of these expected values over all possible bounds um [su < < - *( - )]/ *( - )/ ( )/ ( / )/ assuming that we are very lucky and always happen to select the median as the boundthen each partitioning process splits the array in two halvesand the number of necessary passes to sort is log(nthe resulting total number of comparisons is then *log( )and the total number of exchanges is *log( )/ of courseone cannot expect to hit the median all the time in factthe chance of doing so is only / surprisinglyhoweverthe average performance of quicksort is inferior to the optimal case by factor of only *ln( )if the bound is chosen at random but quicksort does have its pitfalls first of allit performs moderately well for small values of nas do all advanced methods its advantage over the other advanced methods lies in the ease with which straight sorting method can be incorporated to handle small partitions this is particularly advantageous when considering the recursive version of the program stillthere remains the question of the worst case how does quicksort perform thenthe answer is unfortunately disappointing and it unveils the one weakness of quicksort considerfor instancethe unlucky case in which each time the largest value of partition happens to be picked as comparand then each step splits segment of items into left partition with - items and right partition with single element the result is that (instead of log( )splits become necessaryand that the worst-case performance is of the order apparentlythe crucial step is the selection of the comparand in our example program it is chosen as the middle element note that one might almost as well select either the first or the last element in these casesthe worst case is the initially sorted arrayquicksort then shows definite dislike for the trivial job and preference for disordered arrays in choosing the middle elementthe strange characteristic of quicksort is less obvious because the initially sorted array becomes the optimal case in factalso the average performance is slightly betterif the middle element is selected hoare suggests that the choice of be made at randomor by selecting it as the median of small sample ofsaythree keys [ and such judicious choice hardly influences the average performance of quicksortbut it improves the worstcase performance considerably it becomes evident that sorting on the basis of quicksort is somewhat like gamble in which one should be aware of how much one may afford to lose if bad luck were to strike there is one important lesson to be learned from this experienceit concerns the programmer directly