Thread: Kth largest &kth smallest

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.