# Thread: Kth largest &kth smallest

1. ## Kth largest &kth smallest

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

2. Please post what you have done so far.

3. If you haven't done anything, think about how you would do it on paper. Describe the steps you would go through.

4. 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]

5. 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.

6. Originally Posted by iMalc
Jamdog doesn't know the O(n) method...
You are quite correct

7. is is that v first sort it in ascending or descending order and the find the kth largest or smallest ?

8. 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.

9. Originally Posted by baffleddreams
is is that v first sort it in ascending or descending order and the find the kth largest or smallest ?
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.

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.
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)).

iMalc's algo sounds intriguing, but I'm not familiar with using Quicksort, like that, either.
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.

10. 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 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.
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.

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).
I suggest that you take a look at the C++ standard library's std::nth_element generic algorithm from <algorithm>.

12. Oh, I read iMalc's post a few times. This part is clear:
the quicksort-style partitioning is done based on a pivot value, not index,
I have experimented with Quicksort up and down the block, so I know it pretty well.

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.

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).
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.

Originally Posted by laserlight
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.
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.

14. Originally Posted by iMalc
Hmm, I don't have a good source for the definition of a partial sort. So I'll take your word for it.
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.

15. ## this is what i have done

i have used the quick sort methord........ im not supposed to use recursion
insert
Code:
```#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;
}```