Explain why it is important to consider running time when coding algorithms. Use an example to illustrate your point. Your example, web-based or not, should deal with a lot of data.

Write a class with an int array as its only instance variable. Write a recursive method that uses the Quick Sort algorithm in order to sort the array. (Quick Sort is explained below.) You will then add the appropriate code and perform the appropriate simulations to evaluate the running time of the method as a function of the number of elements in the array. Here is how Quick Sort works:

Partition the array so that all the elements to the left of a certain index are smaller than the element at that index and all the elements to the right of that index are greater than or equal to the element at that index. You should code a separate method to partition the array. (See explanation that follows.) Sort the left part of the array using Quick Sort (this is a recursive call). Sort the right part of the array using Quick Sort (this is another recursive call)

To partition the array elements in the manner previously explained, you should code another method (this one nonrecursive) as explained in the following:

Choose an element of the array (for example, the first element). We call this element the pivot. This method partitions the array elements so that all the elements left of the pivot are less than the pivot, and all the element right of the pivot are greater than or equal to the pivot. This method returns an int representing the array index of the pivot (after the elements have been partitioned in the order described previously). In order to rearrange the array elements as previously described, implement the following pseudocode.

The following is pseudocode to partition a subarray whose lower index is low and higher index is high:

Using a counter, keep track of the number of statement executions performed when using Quick Sort to sort an array of n elements. In particular, you should run simulation runs on these two situations:

The array is not sorted The array is presorted in the correct order You should perform a mathematical analysis of the running time of Quick Sort in the average case based on its recursive formulation (using iteration, as we did in the chapter examples).