Question

I need help

In the lecture you got acquainted with the median algorithm, which calculates the median of an unsorted array with n∈N elements in O (n). But the algorithm can actually do much more: it is not limited to finding only the median, but can generally find the ith element with 0≤i <n. Implement this generic version of the median algorithm by creating a class selector in the ads.set2.select package and implementing the following method:

/**
 * Returns the number that would be at index {@code index} in a sorted version
 * of the array.
 * 
 * @param numbers array with pairwise distinct numbers.
 * @param index   the index of the number we're looking for in a sorted version
 *                of {@code numbers}.
 * @return the number at the given index.
 * @throws IllegalArgumentException if {@code index} is not valid for the array.
 */
public static int select(int[] numbers, int index) {
        return -1;
}

Form 5-groups as indicated in the script. For inputs with a maximum of 5 elements, you can end the recursion of the algorithm by sorting the input and finding the desired element in this way. Do not use predefined sorting algorithms in this task, but implement everything yourself! The algorithm can be implemented by working each recursive call on a new array. However, creating the new arrays can take a long time. Instead, the algorithm can also be built completely in-place. But this is not a requirement to complete the task successfully.

Answer 1

Algorithm:

Here we have elements in unsorted array .

Lets size of array is N. Its indexing starting from 0 to N-1.

If median is odd. median will be at integral part of N/2 position.

If median is even , median will be average of value at N/2 and (N+1)/2.

So we will calculate the value for some index i that will be pointed to sorted array.

FindElement(array,i)

{

    value=array(i)

    start from index1 =0 and index1 =N-1;

   while(index1<index2)

   {

         do{

                     index1++;

}while(array(index1)<value);

   do{

                     index2--;

}while(array(index2)>=value);

          if(index1<index2)

         {

               SwapElements(array1(index),array1(index2);

         }

    }

SwapElements(array(index2),array(i))

Return array(i)

}

CalculateMedian{

num1,num2

Input N

Input all array elemnts in unsorted manner in array

if N is Odd . Median = FindElement(array,N/2)

if N is Even . Median =(float) (FindElement(array , N/2) + FindElement(array , (N+1)/2) )/2;

print median;

}

FindMedian is Based on calculating element in sorted manner.