Quicksort s o r t uses cmp to compare a pair of objects, and calls swap as before to interchange them

// Quicksortswap: swap v [ i ] and v [ j ] s t a t i c void swap(Object[] v, i n t i,i n t j)

Object temp; temp = v [ i ] ; v[il = v[jl; v [ j l = temp;

Random number generation is done by a function that produces a random integer i n the range 1e f t to r i g h t inclusive: s t a t i c Random rgen = new Random();

// Quicksort rand: r e t u r n random i n t e g e r i n [ l e f t , r i g h t ] s t a t i c i n t rand(int l e f t , i n t r i g h t )

r e t u r n 1e f t + Math abs(rgen nextInt())%(right-left+l)

We compute the absolute value, using Math abs, because Java's random number generator returns negative integers as well as positive The functions sort, swap, and rand, and the generator object rgen are the rnembers of a class Quicksort Finally, to call Quicksort s o r t to sort a S t r i n g array, we would say

String[] s a r r = new StringCn];

Q u i c k s o r t s o r t ( s a r r , 0, sarrlength-1, new Scmp()); This calls s o r t with a string-comparison object created for the occasion

Exercise 2-2 Our Java quicksort does a fair amount of type conversion as items are cast from their original type (like Integer) to Object and back again Experiment with a version of Q u i cksort s o r t that uses the specific type being sorted, to estimate what performance penalty is incurred by type conversions

We've described the amount of work to be done by a particular algorithm in terms of n, the number of elements in the input Searching unsorted data can take time proportional to n; if we use binary search on sorted data, the time will be proportional to logn Sorting times might be proportional to n 2 or nlogn We need a way to make such statements more precise, while at the same time abstracting away details like the CPU speed and the quality of the compiler (and the programmer) We want to compare running times and space requirements of algorithms independently of programming language, compiler, machine architecture, processor speed, system load, and other complicating factors There is a standard notation for this idea, called "0-notation" Its basic parameter is n, the size of a problem instance, and the complexity or running time is expressed as a function of n The "0" is for order, as in "Binary search is O(1ogn); it takes on the order of logn steps to search an array of n items" The notation O( f(n)) means that once n gets large, the running time is proportional to at most f(n), for example, 0 ( n 2 ) or O(n1ogn) Asymptotic estimates like this are valuable for theoretical analyses and very helpful for gross comparisons of algorithms, but details may make a difference in practice For example, a low-overhead 0 ( n 2 ) algorithm may run faster than a high-overhead O(n1ogn) algorithm for small values of n, but inevitably, if n gets large enough, the algorithm with the slower-growing functional behavior will be faster We must also distinguish between worst-case and expected behavior It's hard to define "expected," since it depends on assumptions about what kinds of inputs will be given We can usually be precise about the worst case, although that may be rnisleading Quicksort's worst-case run-time is 0 ( n 2 ) but the expected time is O(n1ogn) By choosing the pivot element carefully each time, we can reduce the probability of quadratic or 0 ( n 2 ) behavior to essentially zero; in practice, a wellimplemented quicksort usually runs in O(n1ogn) time