12/09/2005

Coding Puzzles - 1

  Find the K-th biggest element in an array.

int partition(const int * na, int low, int hight);
int new_qsort(const int * na, int low, int high, int nNeed);
/**
*   find the k-th biggest element in a integer array, using a
*  modified quick sort algorithm.
*
*   Prarameters:
*   narray : the start address of the integer array.
*   n      : the size of the integer array.
*   k      : the priority of the needed element.
*
*   Return Value:
*   -1    : array size error.
*   -2    : k value invalid.
*   other : the index of the k-th biggest element in the array.
*/
int find_orderk(const int * narray, const int n, const int k) {
   if ( n < 1)
       return -1;
    if ( (K < 1)  (K > n) )
       return -2;
    // store a copy of the original int arrray.
   int * pN = new int[n];
   for (int i = 0; i < n; i++)
       pN[i] = narray[i];
    // find the k-th biggest VALUE in the int array.
   int nVal = new_qsort(pN, 0, n-1, k-1);
    // find the first position of the k-th biggest VALUE in the original array.
   for (int i = 0; i < n; i++)
       if ( narray[i] == nVal)
           return i;
};
/** * one pass of standard quik sort. * * Parameters: * na : the start address of the integer array. * low : the lower boundary of the elements needed to be processed. * hight : the upper boundary of the elements needed to be processed. * * Return Value: * the index of the pivot element after this pass. */ int partition(const int * na, int low, int hight) { int nTmp = na[low]; while (low < high ) { while (low < high && na[high] <= nTmp) high--; na[low] = na[high]; while (low < high && na[low] >= nTmp) low++; na[higt] = na[low]; } na[low] = nTmp; return low; }


/**
*       modified qsort, only sort the part that contains the
*  nNeed-th biggest element. The return value is the value of
*  the nNeed-th biggest element, not the position.
*
*   Parameters:
*       na    : the start address of the integer array.
*       low   : the lower boundary of the elements needed to be processed.
*       hight : the upper boundary of the elements needed to be processed.
*       nNeed : the priority of the needed element.
*
*   Return Value:
*       the value of the nNeed-th biggest element in the given integer array.
*/
int new_qsort(const int * na, int low, int high, int nNeed) {
   int nFound = partition(na, low, high);
   if (nFound == nNeed) {
       return na[nFound];
   } if (nFound < nNeed) {
       return new_qsort(na, nFound, high);
   } if (nFound > nNeed) {
       return new_qsort(na, low, nFound);
   }
}