Let ilselect(A, n, i) be an algorithm that selects the i-smallest from an array

Question

Let ilselect(A, n, i) be an algorithm that selects the i-smallest from an array A with n integers. It works as follows:
ilselect(A, n, i)
{
   r=partition(A, 1, n);
   //test if A[r] is the element to be selected if i == r, return A[r];
   //test if quickselect from the low-part
   if i < r, return quickselect(A, 1, r - 1, i);
   //test if linearselect from the high-part
   if i > r, return linearselect(A, r + 1, n, i - r);
}
That is, the algorithm runs quickselect on the low-part or runs linear select on the high-part. Show the average-case space complexity of the algorithm.

Explanation / Answer

#include <stdio.h>
    #include <math.h>
    #include <time.h>
    #define SIZE 10
    #define swap(X,Y) {int temp=X; X=Y; Y=temp;}

    int partition(int array[], int start, int end)
    {
        if(start==end)
            return start;
        if(start>end)
            return -1;
        int pos=end+1,j;
        for(j=start+1;j<=end;j++)
        {     
            if(array[j]<=array[start] && pos!=end+1)
            {
                swap(array[j],array[pos]);
                pos++;
            }
            else if(pos==end+1 && array[j]>array[start])
                pos=j;
        }
        pos--;
        swap(array[start], array[pos]);
        return pos;
    }

    int order_statistic(int array[], int start, int end, int r)
    {
        if(start>end || (end-start+1)<r)
            return -1;                   //return -1
        int pivot=rand()%(end-start+1)+start, position, p;
        swap(array[pivot], array[start]);
        position=partition(array, start, end);
        p=position;
        position=position-start+1;                  //size of left partition
        if(r==position)
            return array[p];
        else if(r<position)
            return order_statistic(array, start,p-1,r);
        else
            return order_statistic(array,p+1,end,r-position);
    }

    void main()
    {
        srand((unsigned int)time(NULL));
        int i, array[SIZE],r;
        printf("Printing the array... ");
        for(i=0;i<SIZE;i++)
            array[i]=abs(rand()%100), printf("%d ",array[i]);
        printf(" r=");
        scanf("%d",&r);
        int k_small=order_statistic(array,0,SIZE-1,r);
        printf(" ");
        if(k_small==-1)
        {
            printf("Not possible ");
            return ;
        }
        printf(" r smallest elements... ");
        for(i=0;i<SIZE;i++)
        {
            if(array[i]<=r_small)
                printf("%d ",array[i]);
        }
    }

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.