Thread: Kth largest &kth smallest

  1. #1
    Registered User baffleddreams's Avatar
    Join Date
    Aug 2010
    Location
    India
    Posts
    15

    Unhappy Kth largest &kth smallest

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

  2. #2
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Please post what you have done so far.

  3. #3
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    If you haven't done anything, think about how you would do it on paper. Describe the steps you would go through.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  4. #4
    Registered User
    Join Date
    Sep 2010
    Location
    Halesowen, England
    Posts
    30
    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. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Sep 2010
    Location
    Halesowen, England
    Posts
    30
    Quote Originally Posted by iMalc View Post
    Jamdog doesn't know the O(n) method...
    You are quite correct

  7. #7
    Registered User baffleddreams's Avatar
    Join Date
    Aug 2010
    Location
    India
    Posts
    15

    Arrow

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

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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.

    Quote Originally Posted by Adak
    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)).

    Quote Originally Posted by Adak
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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).

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    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
    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>.
    Last edited by laserlight; 09-28-2010 at 01:42 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Adak View Post
    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.

    Quote Originally Posted by laserlight View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User baffleddreams's Avatar
    Join Date
    Aug 2010
    Location
    India
    Posts
    15

    Post 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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Largest and smallest of 3 inputs
    By SilentPirate007 in forum C Programming
    Replies: 6
    Last Post: 03-27-2010, 01:27 PM
  2. Replies: 22
    Last Post: 05-29-2009, 05:44 PM
  3. largest and smallest number
    By wise_ron in forum C Programming
    Replies: 11
    Last Post: 10-05-2006, 03:25 PM
  4. Largest / Smallest (5 integers)
    By Ripley in forum C Programming
    Replies: 4
    Last Post: 10-09-2005, 08:58 PM