find k-th small number

findk.c

/*input :A[n]
 * output:k-th large number
 */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define LEN(a) (int)(sizeof(a)/sizeof(a[0]))
#define SWAP(a,b) do{int temp;temp=a;a=b;b=temp;}while(0)
int searchk(int a[],int left,int right,int k);
void print(int a[],int start,int end);
int main(){
    long seed;
    seed=time(NULL);
    srand(seed);

    int a[]={5,1,3,6,8,5,2,5,6,1,8,6,4,3,5};
    int k,kth;
    printf("input k-th number:");
    scanf("%d",&k);
    kth=searchk(a,0,LEN(a)-1,k);
    printf("%dth large is %d\n",k,kth);
    return 0;
}
/*
以[0,n-1]为例解释各个参数的含义
[1,l]<p  l指向最后一个小于p的数
(r,n]>p  r+1指向第一个大于p的数
(l,i)=p
[i,r] 未处理的数
*/
int searchk(int a[],int left,int right,int k){
    int random=rand()%(right-left+1)+left;
    SWAP(a[left],a[random]);
    int pivot=a[left];
    printf("pivot:%d\n",pivot);
    int l=left,r=right;
    int i;
    for(i=left+1;i<=r;i++){
        if(a[i]<pivot){
            l++;
            SWAP(a[l],a[i]);
        }
        else if(a[i]>pivot){
            while(a[r]>pivot && r>=i)// important!!!
                r--;
            if(r>=i){
                SWAP(a[r],a[i]);
                r--;
                if(a[i]<pivot){
                    l++;
                    SWAP(a[l],a[i]);
                }
            }
        }
        //print(a,right-left+1);
    }
    /*
    //SWAP(a[left],a[l]);
    for(i=l+1;i<=r;i++){
        if(a[i]>pivot){
            SWAP(a[r],a[i]);
            r--;
            if(a[i]<pivot){
                l++;
                SWAP(a[l],a[i]);
            }
        }
        else if(a[i]<pivot){
            l++;
            SWAP(a[l],a[i]);
        }
        //print(a,right-left+1);
    }*/
    SWAP(a[left],a[l]);
    //while(a[r]>pivot)
    //    r--;
    printf("%d %d %d %d\n",left+1,l+1,r+1,right+1);
    print(a,left,right);
    int p=k-1;
    if(p>=l && p<=r)
        return a[p];
    else if(p<l)
        return searchk(a,left,l-1,k);
    else
        return searchk(a,r+1,right,k);
}

void print(int a[],int start,int end){
    int i;
    for(i=start;i<=end;i++)
        printf("%d%s",a[i],(i==end)?"\n":" ");
}