Question

1. a) Describe an O(m)-time algorithm that, given a set of S of n distinct numbers and a positive integer k c n, determines the top k numbers in s b) Describe an O(n)-time algorithm that, given a set of S of n distinct numbers and a positive integer k < n, determines the smallest k numbers in S.

Answer 1

1)
//since list elements are distinct
//step1: first we will find the kth largest item using kth order statistic algorithm
int partition(int A[], int low, int high)
    {
        if(low==high)
            return low;
        if(low>high)
            return -1;
        int pos=high+1,j;
        for(j=low+1;j<=high;j++)
        {      
            if(A[j]>=A[low] && pos!=high+1)
            {
                swap(A[j],A[pos]);
                pos++;
            }
            else if(pos==high+1 && A[j]>A[low])
                pos=j;
        }
        pos--;
        swap(A[low], A[pos]);
        return pos;
    }
//finds the kth smallest item
    int order_statistic(int A[], int low, int high, int k)
    {
        if(low>high || (high-low+1)<k)
            return -1;                 
        int pivot=rand()%(high-low+1)+low, position, p;
        swap(A[pivot], A[low]);
        position=partition(A, low, high);
        p=position;
        position=position-low+1;                 
        if(k==position)
            return A[p];
        else if(k<position)
            return order_statistic(A, low,p-1,k);
        else
            return order_statistic(A,p+1,high,k-position);
    }

//step2: after finding the kth largest item, now we will traverse the array to find the remaining largest items//those are greater than kth largest item
//complexity: O(n)
b)
//since list elements are distinct
//step1: first we will find the kth smallest item using kth order statistic algorithm
int partition(int A[], int low, int high)
    {
        if(low==high)
            return low;
        if(low>high)
            return -1;
        int pos=high+1,j;
        for(j=low+1;j<=high;j++)
        {      
            if(A[j]<=A[low] && pos!=high+1)
            {
                swap(A[j],A[pos]);
                pos++;
            }
            else if(pos==high+1 && A[j]>A[low])
                pos=j;
        }
        pos--;
        swap(A[low], A[pos]);
        return pos;
    }
//finds the kth smallest item
    int order_statistic(int A[], int low, int high, int k)
    {
        if(low>high || (high-low+1)<k)
            return -1;                 
        int pivot=rand()%(high-low+1)+low, position, p;
        swap(A[pivot], A[low]);
        position=partition(A, low, high);
        p=position;
        position=position-low+1;                 
        if(k==position)
            return A[p];
        else if(k<position)
            return order_statistic(A, low,p-1,k);
        else
            return order_statistic(A,p+1,high,k-position);
    }

//step2: after finding the kth smallest item, now we will traverse the array to find the remaining smallest items//those are less than kth small item
//complexity: O(n)