Partition an array for use with 'ksmall' algorithm

Subject:Computer SciencePrice:2.87 Bought7

Share With

Partition an array for use with 'ksmall' algorithm. For this task you have to write the C function, partition_array(), that partitions the data around a pivot value. You will be implementing Step 1 of a famous algorithm 'ksmall' for this task. The algorithm has two basic steps. Step 1: Partition the data around a pivot value such that all the elements to the left of pivot index are smaller than the pivot value and the ones to the right are greater than the pivot value. Step 2: Recursively call the function 'kSmall()', on the partition that contains the kth smallest element. Details are given in the attached document. (you don't have to worry about this step) For this task you will develop the function partition_array(). The partition algorithm chooses some element p (called the pivot), then rearranges the array such that: • All elements less than or equal to p are before p. • All elements greater than p are after p. • p is in the position it would occupy if the array were sorted. • The algorithm then returns the index of p. • For this implementation your algorithm will always choose the last element of the input array as pivot. It has the following prototype: int partition_array(float * ptr_array, int size);