Can anyone help me 2 find d kth largest &kth smallest element in an array?

Printable View

- 09-25-2010baffleddreamsKth largest &kth smallest
Can anyone help me 2 find d kth largest &kth smallest element in an array?

- 09-25-2010kmdv
Please post what you have done so far.

- 09-25-2010claudiu
If you haven't done anything, think about how you would do it on paper. Describe the steps you would go through.

- 09-25-2010Jamdog
I'd probably create a 2nd array, sort the 1st array into the 2nd (to make a sorted array). You can then easily find the 'kth' largest and smallest with

**sorted_array[(k-1)]**and**sorted_array[num_elements-k]** - 09-25-2010iMalc
Jamdog doesn't know the O(n) method...

Use quicksort partitioning steps but only recurse on the portion that contains index k. The array ends up partially sorted, just enough to get the kth element into position k.

You've got to do some work before you get anything more than that. - 09-25-2010Jamdog
- 09-27-2010baffleddreams
is is that v first sort it in ascending or descending order and the find the kth largest or smallest ?

- 09-27-2010Adak
For a general algorithm, I'm thinking of 2 "buckets". Low 10, and Top 10. Run through the values, and put the lowest and highest 10 values, into their respective "buckets". Whenever you find a new low 10 value, you add that value, and bump out the highest value in the Low 10 bucket. Whenever you find a new high 10 value, you add that value, and bump out the lowest Top 10 value.

Buckets would be either values or indeces, in small 10 element arrays. iMalc's algo sounds intriguing, but I'm not familiar with using Quicksort, like that, either. - 09-28-2010laserlightQuote:

Originally Posted by**baffleddreams**

Quote:

Originally Posted by**Adak**

Quote:

Originally Posted by**Adak**

- 09-28-2010Adak
That works for a dividing up the array by a value, but you can't get a specific number (10, 20, 100, whatever) of values, by just partitioning. If you don't count and manage the partitions or buckets, you won't know how many values are in each of them.

Say I want everything less than 50 or more than 75, in an array - partitioning is fine. But it won't give me the top 10 values in the array, without some managing and discarding when the number of values in the partition or bucket, becomes more than 10 (or whatever). - 09-28-2010laserlightQuote:

Originally Posted by**Adak**

Quote:

Originally Posted by**Adak**

- 09-28-2010Adak
Oh, I read iMalc's post a few times. This part is clear:

Quote:

the quicksort-style partitioning is done based on a pivot value, not index,

I'll give it a look see when I'm not being beat up by the sandman.

Thanks for the info on getting a look at it, in the C++ standard library. - 09-28-2010iMalc
No, I assure you, using the quicksort-like technique is the standard way of finding the Kth item. It works if you follow my description. Just looked up the name of it and it's Hoare's selection algorithm.

Hmm, I don't have a good source for the definition of a partial sort. So I'll take your word for it.

That's the minimum you can say about what it does, but in practice due to the fact that it performs multiple recursive calls, the items end up arranged in several consecutive chunks where all the items in a particular chunk are no less that the items from the previous chunk, and no greater than the items in the next chunk. Chunks vary greatly in sizes of course.

In effect, you're a reasonable amount closer to the goal of having the array sorted, moreso than if you look at it from the point of view of it always being merely a single partitioning based jsut on the particular element of interest.

In this way, it is indeed partially sorted. Assuming of course that you picked an algorithm that could take advantage of what has already been done when performing the remaining sorting.

That may very well differ from the definition of a partial sort, which I believe possibly involves actually having certain portions of the array in order afterwards. - 09-28-2010laserlightQuote:

Originally Posted by**iMalc**

- 10-01-2010baffleddreamsthis is what i have done
i have used the quick sort methord........ im not supposed to use recursion

insertCode:`#include<stdio.h>`

#include<conio.h>

int main()

{

int x[20],n,i,k;

printf("\nEnter size of the array :");

scanf("%d",&n);

printf("\nEnter %d elements :",n);

for(i=0;i<n;i++)

scanf("%d",&x[i]);

int p,j,temp,first=0,last=n-1;

segment1:

while(first<last)

{

p=first;

i=first;

j=last;

while(i<j)

{

while(x[i]<=x[p]&&i<last)

i++;

while(x[j]>x[p])

j--;

if(i<j)

{

temp=x[i];

x[i]=x[j];

x[j]=temp;

}

}

temp=x[p];

x[p]=x[j];

x[j]=temp;

while((i+j)/2)

{

last=j-1;

goto segment1;

}

}

first=j+1;last=n-1;

segment2:

while(first<last)

{

p=first;

i=first;

j=last;

while(i<j)

{

while(x[i]<=x[p]&&i<last)

i++;

while(x[j]>x[p])

j--;

if(i<j)

{

temp=x[i];

x[i]=x[j];

x[j]=temp;

}

}

temp=x[p];

x[p]=x[j];

x[j]=temp;

while((i+j)/2)

{

first=j+1;

goto segment2;

}

}

printf("\nThe sorted array");

for(i=0;i<n;i++)

printf(" %d",x[i]);

getch();

return 0;

}