Question

Hi, I am having trouble with the following question:

Given an unsorted array with integers, find the median of it using the Quick Select method we’ve discussed in the class (Hint: We use the quick select to find the kth smallest element in an unsorted array in O(n) time complexity). Note: A median is the middle number of the array after it is sorted. And in this problem, we return the N/2-th number after sorted if there are even numbers in the array. Do not sort the array to find the median!

Answer 1

Algorithm

Algorithm kthSmallest(arr[],l, r, k)

// This algorithm returns k'th smallest element in arr[l..r] usingQuickSort based method. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT

{

    // If k is smaller than number of elements in array

    if (k > 0 && k <= r - l + 1)

    {

        // Partition the array around last element and get position of pivot element in sorted array

        pos = partition(arr, l, r);

        // If position is same as k

        if (pos-l = = k-1)

            return arr[pos];

        if (pos-l > k-1) // If position is more, recur for left subarray

            return kthSmallest(arr, l, pos-1, k);

        // Else recur for right subarray

        return kthSmallest(arr, pos+1, r, k-pos+l-1);

    }

    // If k is more than number of elements in array

    return INT_MAX;

}

Algorithm swap( a, b)

{

    temp = a;

    a = b;

    b = temp;

}

Algorithm partition(arr[],l, r)

// Partition process of QuickSort(), considers the last element as pivot and moves all smaller element to left of it and greater elements to right

{

    x = arr[r], i = l;

    for (j = l; j <= r - 1; j++)

    {

        if (arr[j] <= x)

        {

            swap(arr[i], arr[j]);

            i++;

        }

    }

    swap(arr[i], arr[r]);

    return i;

}

Algorithm findMedian()

{

    Input array of size n

//Median is middle element when n is odd and average of middle two elements when n is even.

if (n%2==0)                           

    {

        k=n/2;

         Output median=kthSmallest(arr, 0, n-1, k);

    }

    else

    {

      k=(n-1)/2;

     a=kthSmallest(arr, 0, n-1, k);

      b=kthSmallest(arr, 0, n-1, (k+1));

       Output median = (a+b)/2.

    }   

}

Complexity of this algorithm is O(n).