while loop would be required to bump the pointers the nop version is the most efficient solution efficiency of the partition algorithm the partition algorithm runs in (ntime it' easy to see this when running the partition workshop appletthe two pointers start at opposite ends of the array and move toward each other at more or less constant ratestopping and swapping as they go when they meetthe partition is complete if there were twice as many items to partitionthe pointers would move at the same ratebut they would have twice as far to go (twice as many items to compare and swap)so the process would take twice as long thus the running time is proportional to more specificallyfor each partition there will be + or + comparisons every item will be encountered and used in comparison by one or the other of the pointersleading to comparisonsbut the pointers overshoot each other before they find out they've "crossedor gone beyond each otherso there are one or two extra comparisons before the partition is complete the number of comparisons is independent of how the data is arranged (except for the uncertainty between and extra comparisons at the end of the scanthe number of swapshoweverdoes depend on how the data is arranged if it' inversely ordered and the pivot value divides the items in halfthen every pair of values must be swappedwhich is / swaps (remember in the partition workshop applet that the pivot value is selected randomlyso that the number of swaps for inversely sorted bars won' always be exactly / for random datathere will be fewer than / swaps in partitioneven if the pivot value is such that half the bars are shorter and half are taller this is because some bars will already be in the right place (short bars on the lefttall bars on the rightif the pivot value is higher (or lowerthan most of the barsthere will be even fewer swaps because only those few bars that are higher (or lowerthan the pivot will need to be swapped on averagefor random dataabout half the maximum number of swaps take place although there are fewer swaps than comparisonsthey are both proportional to thus the partitioning process runs in (ntime running the workshop appletyou can see that for random bars there are about swaps and comparisonsand for random bars there are about swaps and comparisons quicksort quicksort is undoubtedly the most popular sorting algorithmand for good reasonin the majority of situationsit' the fastestoperating in ( *logntime (this is only true for internal or in-memory sortingfor sorting data in disk files other methods may be better quicksort was discovered by hoare in to understand quicksortyou should be familiar with the partitioning algorithm described in the last section basically the quicksort algorithm operates by partitioning an array into two subarraysand then calling itself to quicksort each of these subarrays howeverthere are some embellishments we can make to this basic scheme these have to do with the selection of the pivot and the sorting of small partitions we'll examine these refinements after we've looked at simple version of the main algorithm it' difficult to understand what quicksort is doing before you understand how it does itso we'll reverse our usual presentation and show the java code for quicksort before presenting the quicksort workshop applet the quicksort algorithm