3. b) Kth Largest element.

3.b) Find the K^th Largest element in the array.

Problem link :- ಸಿಕ್ಕಿದರೆ ಕಳುಹಿಸಿ

//kth largest element
#include<stdio.h>

void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int A[], int start, int end)
{
    int pivot, i, j;

    pivot = A[end];
    i = start - 1;
    j = start;

    for(j=start; j<end; j++)
    {
        if(A[j] < pivot)
        {
            i++;
            swap(&A[i], &A[j]);
        }
    }
    i++;
    swap(&A[i], &A[end]);
    return i;
}



int kth_largest(int A[], int start, int end, int k)
{
    int pos, length;

	if(start < end)
    {
    	pos = partition(A, start, end);
    	length = pos + 1;

    	if(k == length)
        	return A[pos];
    	if(k < length)
        	return kth_largest(A, start, pos-1, k);
    	else
        	return kth_largest(A, pos+1, end, k);
    }
}


void main()
{
    int arr1[30];
    int n, i;
    int k, ans, corrk;

    printf("Enter the size of the array\n");
    scanf("%d",&n);
    printf("Enter the elements of the array\n");
    for(i=0; i<n; i++)
        scanf("%d",&arr1[i]);

    printf("Enter a integer less than %d\n",n);
    scanf("%d",&k);


    printf("Given Array\n");
    for(i=0; i<n; i++)
        printf("\t%d",arr1[i]);
    printf("\n");


    corrk = n - k + 1;

    ans = kth_largest(arr1, 0, n-1, corrk);
    printf("\n\n%d Largest element in the array is %d\n\n", k, ans);
}