Friday, 26 October 2012

Kth SMALLEST ELEMENT


Q.) FIND THE KTH SMALLEST ELEMENT IN A GIVEN ARRAY .
SOLUTION--







#include
#include
using namespace std;
int main()
{
    int n,k,i,min;
    printf("enter the size of array=");
    scanf("%d",&n);
    int arr[n];
    printf("the velue of k=");
    scanf("%d",&k);
    for(i=0;i
        scanf("%d",&arr[i]);
    sort(arr,arr+k);
    min=arr[k-1];
    for(i=k;i
    {
        if(arr[i]
        {
            arr[k-1]=arr[i];
            sort(arr,arr+k);
            min=arr[k-1];
        }
    }
    printf("%dth smallest element in array=%d",k,arr[k-1]);
    return 0;
}

1 comment:

CHANDAN SINGH said...

EXPLAINATION--

Step 1 From first K numbers build a max heap so that the top element is largest in those K numbers. Say that element is X.
Step 2 Now as numbers are coming for processing, say coming number be A
If A>X then A cant be Kth smallest.
If A=X then no change is needed.
If A6 so we will neglect 8. When 3 will come since 3<6 we will replace 6 with 3 in the heap and again we will call heapify. After heapify 5 will be on the top. When 2 will come, 2<5 then 5 will be replaced by 2 and after heapification 3 will be on the top. When 4 will come since 4>3 then we will neglect the 4. Now at the end 3 is on the top of the heap so 3 is the3rd smalle st element of the given numbers or array.

NOTE-For Kth largest build min heap