Chapter 9, Problem 1P

(a)

Program Plan Intro

To describe the algorithm that sorts the number to list the largest and also give the running time of the algorithm.

Explanation of Solution

The algorithm that sort the number by finding the largest number from the list is based on the dividing the list into some part to find the largest from the number and then divide the whole list into two parts that is, one part consists of largest number and other part consists rest of the numbers.

The algorithm uses the largest number and find the correct position of that number by comparing to all the number then it find the largest number from the rest of the number.

The algorithm placed that largest number to their correct position and allows this procedure until the last element is remaining in the array then combined all the number as it is placed by the algorithm and the merged array consists of sorted number.

The dividing of number takes the time of $\lg n$ with the linear time equals to the size of the array and the listing of the elements takes constant time of i.

Therefore, it takes total time of $O(n\lg n+i)$ .

(b)

Program Plan Intro

To describe the algorithm that built a max-priority queue by calling EXTRACT-MAX and also gives the running time of the algorithm.

Explanation of Solution

The algorithm that uses max-priority queue and calling the EXTRACT-MAX is the Heap-sort. The algorithm is based on the creating the in-order tree by the numbers and calls the MAX-HEAPIFY at the nodes that are not leaf.

The algorithm arranged the tree in such a way that the root of the tree has largest number then the algorithm removes the root and stores it in the priority queue.

The algorithm again calls the EXTRACT-MAX on the remaining tree and arranged the tree such that root has largest number and remove the root and stored to the priority-queue where previous element is stored and continued the procedures again and again until the tree has only no elements.

The EXTRACT-MAX algorithm extracts the maximum or largest number from the given number by calling MAX-HEAPIFY.

The heapify of the algorithm takes the time of $n\lg n$ and the extraction takes the time of $\lg n$ as it considered the whole tree with height $\lg n$ .

Therefore, the running time of the algorithm is $O(n\lg n)$ where $n=size+i$ .

(c)

Program Plan Intro

To describe the algorithm that uses an order-statistic algorithm to find the largest, partition around that number and also give the running time of the algorithm.

Explanation of Solution

The algorithm considers all the numbers and stores the number into an array. It selects the largest by comparing the numbers and uses the finding function to find the largest number that is based on the comparisons of the numbers.

Then the algorithm partition the array into several parts using the partition algorithm. The partition algorithm recursively called itself and compared the element until it partitioned the array into single elements.

After the partition the algorithm merged the subparts in the sorted order of array that is i times. The merging of all the sorte3d parts gives the array of sorted number that is the output of the algorithm.

The finding and partition of the i -array takes the linear time of n . The sorting of the sub-parts of the array is based on the dividing and merging that takes the time of $i\lg i$ where i is the i -largest number.

Therefore, the algorithm takes total running time of $O(n+i\lg i)$ .