Finding the Kth smallest element in an array using recursion
I am working on a problem that requires me to determine the Kth smallest element in an array using recursion. I've written 2 programs to do that, both are based on the partitioning of the array based on selecting a pivot element (elements less than on one side and greater than on the other side), but both seem to be giving wrong answers. I need help with the codes.......
Program 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);
}
Program 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);
}
}
