Can anyone help me 2 find d kth largest &kth smallest element in an array?
Printable View
Can anyone help me 2 find d kth largest &kth smallest element in an array?
Please post what you have done so far.
If you haven't done anything, think about how you would do it on paper. Describe the steps you would go through.
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]
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.
is is that v first sort it in ascending or descending order and the find the kth largest or smallest ?
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.
If you intend to sort, then either ascending or descending order will do. It should be obvious to you that once the elements are sorted, whichever way it is sorted, finding the kth largest and kth smallest is just a matter of selecting the elements at the given indices.Quote:
Originally Posted by baffleddreams
This is good in that you only make a single pass over the array. However, if k (which may not be 10) is sufficiently large, the time taken to add the new value and/or "bump out" the value to be discarded would become significant (i.e., the time complexity would then be worse than O(n)).Quote:
Originally Posted by Adak
If you know quicksort, I think iMalc's description is sufficient, but note that this is not a partial sort. Rather, it is a partitioning such that the kth element is placed in its position between a partition of elements less than its value, and another partition of elements greater than its value.Quote:
Originally Posted by Adak
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).
That is a misconception; you must have missed this part of iMalc's description: "only recurse on the portion that contains index k." Yes, the quicksort-style partitioning is done based on a pivot value, not index, but the overall idea behind the kth element algorithm is to create two partitions based on the index k, with the element at index k in between them (as I described earlier). That is why during the partitioning process one can ignore the partition that does not contain the index k, because the elements of that partition must belong to one of these two final partitions that do not contain the index k.Quote:
Originally Posted by Adak
I suggest that you take a look at the C++ standard library's std::nth_element generic algorithm from <algorithm>.Quote:
Originally Posted by Adak
Oh, I read iMalc's post a few times. This part is clear:
I have experimented with Quicksort up and down the block, so I know it pretty well.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.
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.
I'm thinking along the lines of std::partial_sort from the C++ standard library's <algorithm> header, i.e., to sort only part of a range rather than the entire range. After all, std::partial_sort is another way of tackling the problem, yet it also does more work than required.Quote:
Originally Posted by iMalc
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;
}