Thread: Finding the Kth smallest element in an array using recursion

Indent style - Wikipedia, the free encyclopedia
Pick an indent style other than "none"
Nobody wants to look at code looking like that.

Sorry for absence of indentation, i had written the code in notepad so there was no indentation. Here are the codes (with indentation).
1.

Code:

#include<stdio.h>
#include<stdlib.h>
#define MAX 10
int find(int ar[],int low,unsigned int high,int k);
int length(int ar[]);
int main()
{
    int ar[MAX],k,ans;
    register int i=0;
    printf("\nPlease enter the numbers in the array");
    while(i<MAX){
        scanf("%d",&ar[i]);
        i++;
        }
    printf("\nPlease enter the value of k ");
    scanf("%d",&k);
    ans=find(ar,0,MAX-1,k);
    printf("\nThe %d smallest element in the array is %d",k,ans);
    return 0;
}
int find(int ar[],int low,unsigned int high,int k)
{
    int mid;
    mid=(low+high)/2;
    unsigned int i,j;
    int p[MAX],q[MAX];
    for(i=0,j=0;i<length(ar);i++){
        if(ar[i]<ar[mid]){
            p[j]=ar[i];
            j++;
            }
    }
    for(i=0,j=0;i<length(ar);i++){
        if(ar[i]>ar[mid]){
            q[j]=ar[i];
            j++;
            }
    }
    if(length(p)>=k){
        find(p,0,length(p)-1,k);
        }
    else if(length(p)==k-1){
        return (ar[mid]);
        }
    else{
        find(q,0,length(q)-1,k-mid+1);
        }
}
int length(int ar[])
{
    return(sizeof(ar)/4);
}

2.

Code:

#include<stdio.h>
#include<stdlib.h>
#define MAX 10
int select(int ar[],int low, int high,int k);
int partition(int ar[],int left,int high,int pivot);
int main()
{
    int ar[MAX],k,ans;
    register int i=0;
    printf("\nPlease enter the numbers in the array");
    while(i<MAX){
        scanf("%d",&ar[i]);
        i++;
        }
    printf("\nPlease enter the value of k ");
    scanf("%d",&k);
    ans=select(ar,0,MAX-1,k);
    printf("\nThe %d smallest element in the array is %d",k,ans);
    return 0;
}
int partition(int ar[],int low,int high,int pivot)
{
    register int i;
    int storeindex,temp,pivotvalue;
    pivotvalue=ar[pivot];
    temp=ar[pivot];
    ar[pivot]=ar[high];
    ar[high]=temp;
    storeindex=low;
    for(i=low;i<(high-1);i++)
    {
        if(ar[i]<pivotvalue){
            temp=ar[storeindex];
            ar[storeindex]=ar[i];
            ar[i]=temp;
            storeindex++;
            }
    }
    temp=ar[high];
    ar[high]=ar[storeindex];
    ar[storeindex]=temp;
    return(storeindex);
}
int select(int ar[],int low,int high,int k)
{
    int mid,newpivotindex;
    mid=(low+high)/2;
    newpivotindex=partition(ar,low,high,mid);
    if(k<newpivotindex){
        return select(ar,low,newpivotindex-1,k);
        }
    else if (k==newpivotindex){
        return (ar[k]);
        }
    else{
        return select(ar, newpivotindex+1, high, k-newpivotindex-1);
        }
}

You know you can actually press the space bar in notepad and indent...

Code:

int length(int ar[])
{
    return(sizeof(ar)/4);
}

You cannot get the size of an array passed to a function using the sizeof operator. All it's going to give you is the size of the pointer to the first element (and in this case, divide that by four).

Also, you seem to be assuming that the values are entered in a sorted order.


Quzah.

Originally Posted by itCbitC

That's a well-known sorting program called quicksort and in your case, once the array is sorted, you also need to print out the kth smallest element.

Judging by the title & the post, probably not. There's an algorithm to select the K'th element of an unsorted array - it runs in O(n) time. Faster than a quicksort, but doesn't sort your array. (If you used it for sorting, you'd get O(n^2), so quicksort wins there.)

I was going by the description of the algorithm that the o/p provided, which closely mirrored quicksort.
IMO too the o/p should use the algorithm that finds the kth smallest element w/o sorting to reduce runtime.

Edit:: @Cactus_Hugger: can you post a link or some info on that algorithm.

Originally Posted by itCbitC

I was going by the description of the algorithm that the o/p provided, which closely mirrored quicksort.
IMO too the o/p should use the algorithm that finds the kth smallest element w/o sorting to reduce runtime.

Edit:: @Cactus_Hugger: can you post a link or some info on that algorithm.

He is, that's what the select function he wrote does.

I don't think Cactus_Hugger is correct about the running time of the algorithm though, if we're talking about "Hoare's selection algorithm". It is worse than O(n) worst case, like quicksort, when the partitions are often very unequal. That still means log n recursions on average and n-1 at worst. Introselect is better.

Ah, here it is:
Selection algorithm - Wikipedia, the free encyclopedia