/*Adobe Elitmus Written Test on 27-10-2013 @Bangalore - Algo/DS questions
*Question 2
*/
/*
* In a given set of elements(any order), find K largest numbers
* e.g arr[]={1,4,5,108,10,14,90,43,100} let K=3
* Ouput = {108,100,90}
*/
/*Approach: Modified Bubble Sort
* As we know that bubble sort in Ith pass places the ith largest number at last
* After Kth pass, the results will be available and no need to sort further
*/
#include<stdio.h>
#include<stdlib.h>
//Its Modified Bubble sort
void FindKLargestNumbers(int arr[], int n, int K, int output[])
{
int i,j,count,tmp;
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(arr[j]>arr[j+1])
{
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
if(i==K) break; // K largest numbers are bubbled at top(last indices)
}
count=0;
for(i=n-1;i>=n-K;i--)
{
output[count++]=arr[i];
}
}
void PrintKLargestNuners(int output[] ,int K)
{
int i;
printf("The K=%d largest numbers in the given array are\n",K
); for(i=0;i<K;i++)
{
}
}
int main()
{
int n=9;//no of elements in the array
int K=3;//largest K numbers
int arr[9]={1,4,5,108,10,14,90,43,100};
int output[3];//output array
FindKLargestNumbers(arr,n,K,output);
PrintKLargestNuners(output,K);
return 0;
}
LypBZG9iZSBFbGl0bXVzIFdyaXR0ZW4gVGVzdCBvbiAyNy0xMC0yMDEzICBAQmFuZ2Fsb3JlIC0gQWxnby9EUyBxdWVzdGlvbnMKICpRdWVzdGlvbiAyCiAqLwoKLyoKICogSW4gYSBnaXZlbiBzZXQgb2YgZWxlbWVudHMoYW55IG9yZGVyKSwgZmluZCAgSyBsYXJnZXN0IG51bWJlcnMKICogZS5nIGFycltdPXsxLDQsNSwxMDgsMTAsMTQsOTAsNDMsMTAwfSBsZXQgSz0zCiAqIE91cHV0ID0gezEwOCwxMDAsOTB9CiAqLwoKLypBcHByb2FjaDogTW9kaWZpZWQgQnViYmxlIFNvcnQKICogQXMgd2Uga25vdyB0aGF0IGJ1YmJsZSBzb3J0IGluIEl0aCBwYXNzIHBsYWNlcyB0aGUgaXRoIGxhcmdlc3QgbnVtYmVyIGF0IGxhc3QKICogQWZ0ZXIgS3RoIHBhc3MsIHRoZSByZXN1bHRzIHdpbGwgYmUgYXZhaWxhYmxlIGFuZCBubyBuZWVkIHRvIHNvcnQgZnVydGhlcgogKi8KCiNpbmNsdWRlPHN0ZGlvLmg+CiNpbmNsdWRlPHN0ZGxpYi5oPgoKLy9JdHMgTW9kaWZpZWQgQnViYmxlIHNvcnQKdm9pZCBGaW5kS0xhcmdlc3ROdW1iZXJzKGludCBhcnJbXSwgaW50IG4sIGludCBLLCBpbnQgb3V0cHV0W10pCnsKCWludCBpLGosY291bnQsdG1wOwoKCWZvcihpPTA7aTxuO2krKykKCXsKCQlmb3Ioaj0wO2o8bi0xO2orKykKCQl7CgkJCWlmKGFycltqXT5hcnJbaisxXSkKCQkJewoJCQkJdG1wPWFycltqXTsKCQkJCWFycltqXT1hcnJbaisxXTsKCQkJCWFycltqKzFdPXRtcDsKCQkJfQoJCX0KCQlpZihpPT1LKSBicmVhazsgLy8gSyBsYXJnZXN0IG51bWJlcnMgYXJlIGJ1YmJsZWQgYXQgdG9wKGxhc3QgaW5kaWNlcykKCX0KCgljb3VudD0wOwoJZm9yKGk9bi0xO2k+PW4tSztpLS0pCgl7CgkJb3V0cHV0W2NvdW50KytdPWFycltpXTsKCX0KCn0KCnZvaWQgUHJpbnRLTGFyZ2VzdE51bmVycyhpbnQgb3V0cHV0W10gLGludCBLKQp7CglpbnQgaTsKCQoJcHJpbnRmKCJUaGUgSz0lZCBsYXJnZXN0IG51bWJlcnMgaW4gdGhlIGdpdmVuIGFycmF5IGFyZVxuIixLKTsKCWZvcihpPTA7aTxLO2krKykKCXsKCQlwcmludGYoIiVkICIsb3V0cHV0W2ldKTsKCX0KCXByaW50ZigiXG4iKTsKfQoKCgppbnQgbWFpbigpCnsKCWludCBuPTk7Ly9ubyBvZiBlbGVtZW50cyBpbiB0aGUgYXJyYXkKCWludCBLPTM7Ly9sYXJnZXN0IEsgbnVtYmVycwoJaW50IGFycls5XT17MSw0LDUsMTA4LDEwLDE0LDkwLDQzLDEwMH07CglpbnQgb3V0cHV0WzNdOy8vb3V0cHV0IGFycmF5CgoJRmluZEtMYXJnZXN0TnVtYmVycyhhcnIsbixLLG91dHB1dCk7CgoJUHJpbnRLTGFyZ2VzdE51bmVycyhvdXRwdXQsSyk7CgoJcmV0dXJuIDA7Cn0KCQo=