c - クイック選択を使用して k 番目のパーセンタイル数を見つける方法

Question

整数配列を指定すると、90 パーセンタイルは、配列の 90% を超える最初の数値です。より具体的な定義が必要な場合は、http://studentnet.cs.manchester.ac.uk/ugt/COMP26120/lab/ex6def.htmlをご覧ください。

通常の状況で正常に動作するクイック選択プログラムを作成しました。それは、90パーセンタイルが含まれる側だけをソートする部分ソートです。

ただし、すべての整数が同じで、90 パーセンタイルがない場合などの特別な場合には、90 番目の数値は検索されますが、-1 は返されません。

修正後、プログラムが O(n) であることを確認してください。

(k-1) 番目の数値と k 番目の数値を比較するためにクイック セレクト関数を繰り返し呼び出すメイン関数でループを使用した場合、実行時間は (nk)*n=O(n^2) になります (クイック セレクトは O (n) googled) 選択中に有効な 90 番目の数字を簡単に見つける方法はありますか?

Here are my codes:
#include <stdio.h>
#include <math.h>
#include <stdlib.h>  
#define N 23

void swap ( int *a, int *b){
    int t;
    t=*a;
    *a=*b;
    *b=t;
}
int partition(int *a, int high){ //high is the last index of this array
    int i,j,pivotValue;
    i = -1;
    j = 0;
    pivotValue = a[high]; 
    for ( j=0; j<high; j++){
        if ( a[j]> pivotValue){
            continue;
        }
        i++;
        swap(&a[i], &a[j]);
    }
    return i+1;
}
int quickSelect(int a[],int n, int k) { //n is the size of the array
    int pivotIndex;
    pivotIndex = partition(a, n-1);
    if ( pivotIndex >= k ){//left.size = pivotIndex
        printf("left\n");

        return quickSelect(a, pivotIndex, k);
    }
    else if ( (pivotIndex+1)==k ){
        printf("pivot\n");
        return a[n-1];
    }
    else{
        printf("right\n");
        return quickSelect(&a[pivotIndex], n-(pivotIndex+1), k-(pivotIndex+1));
    }
}


int main()
{
int a[] = {1612,1894,3018,4212,6046,12894,13379,14408,14615,16394,17982,23004,27588,31393,33195,39526,54326,54566,60000,60000,60000,60000,703908};

    int find,k;

    k = floor(N*0.9)+1;
    printf("k=%d\n",k);

    find = quickSelect(a, N, k);

    printf("the 90th number=%d\n",find);

    return 0;
}