With the following set of problems we will develop a divide and conquer based algorithm for the
Question:
With the following set of problems we will develop a divide and conquer based algorithm for the general problem of selection of an order statistics of an array.
The SELECT(A, k) problem asks to find the k smallest element of an array, i.e. an element x which will be at the kth position when A is sorted (or there are k -1 numbers in A smaller than x). More formally,
Input An array A of n distinct integers and an integer k.
Output A number x ∈ A, such that rank A (x) = k.
This is a general problem in the sense that many order statistics or ordering problems can be solved with this.
Problem 1. Briefly, describe an algorithm to find the minimum, median, maximum of an array A using a subroutine for SELECT(A, k).
Problem 2. Briefly, describe an algorithm to sort an array A using a subroutine for SELECT(A, k).
Managerial economics applications strategy and tactics
ISBN: 978-1439079232
12th Edition
Authors: James r. mcguigan, R. Charles Moyer, frederick h. deb harris