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

1. ## 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);
}
}```

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

3. 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);
}
}```

4. 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.

5. Book recomendation that addresses this very matter..."Algorithms in C"

Amazon.com: Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd Edition) (Pts. 1-4): Robert Sedgewick: Books

Your code is a bit overwhelming to accomplish this task.

6. 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.

7. 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.)

8. 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.

9. 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

Popular pages Recent additions