Kth largest &kth smallest

This is a discussion on Kth largest &kth smallest within the C Programming forums, part of the General Programming Boards category; in this above program ive just done partitioning....now how do i find the kth largest and the kth smallest element?...

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

    Question .......

    in this above program ive just done partitioning....now how do i find the kth largest and the kth smallest element?

  2. #17
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I'm VERY surprised that you chose a Quickselect type of partitioning algorithm, when - lo and behond - you say you can't recurse! (news to us, btw).

    Anyway, let's take an example:

    You want to study the top 10 banks in the country, aiming to improve your banks business efficiency. Also, you want to study the bottom 10 banks, for a possible buy out.

    In other words, you're like George Sorros and you have mega-bucks in hand-outs from the gov't, meant to help stimulate bank loans, but you can now use that hand out to buy out small local banks that were making loans, and put them out of business. Hell with making loans. Thanks Democrats - you're idiots, but I digress.

    So in your partitioning, you have a:
    Code:
    pivot = (banks[lo] + banks[hi])/2;
    someplace either before the main loops, if you recurse, or at the top of the loop, if you don't recurse.

    and if I understand it rightly, you need the partitioning to stop when the index of the pivot, equals the kth number. If you want the top 10, you set your goalIndex equal to 10, and when goalIndex >= your hi variable, then you know you have the right data, between banks[0] and banks[goalIndex]. No more partitioning is needed.

    If your banks[] had 100 elements, you might have partitions of 60, 28, 11, and 4. When the hi variable was 4, you can break out - no further work is needed, unless you want the whole array, sorted, so other data can be found quickly.

    If you need your sub array sorted (as would normally be the case for a top 10 list), I'd call insertion sort with the sub array Insertion(banks, 0, goalIndex), and let it do the sorting - for small arrays, it's faster than Quicksort, and has no natural recursion.

    This is the fastest sorter for small sub arrays, that I have found:
    Code:
    /*
    void insertionSort(int *A, int lo, int hi) {
      int i, j, val; 
      j=hi;   
      for(i=lo+1;i<hi;i++) {
        val = A[i];
        j = i-1;
        while(A[j] > val) {
          A[j + 1] = A[j];
          --j;
        }   
        A[j+1] = val;
      }
      puts("\nAfter Insertion Sort:\n");
      for(i=lo;i<hi;i++)
        printf(" %2d ",A[i]);
      getchar();
    
    }
    Check this out, because I haven't done this k selection type problem, before.
    Last edited by Adak; 10-01-2010 at 05:11 PM.

Page 2 of 2 FirstFirst 12
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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21