Problem statement
Write a c program to find kth element in an array without fully sorting the array
(hint: use quick sort )
#include<stdio.h>
#include<stdlib.h>
void quickSort(int a[], int kth,int low, int high);
int partition(int a[],int low, int high);
int main()
{
int *a,n,i,kth;
printf("enter the number of elements ");
scanf("%d",&n);
a=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
printf("enter element ");
scanf("%d",&a[i]);
}
printf("enter the k ");
scanf("%d",&kth);
if(kth<n)
quickSort(a,kth-1,0,n-1);
else
printf("does not exist ");
return 0;
}
void quickSort(int a[], int kth,int low, int high)
{
int p;
if(low<high)
{
p=partition(a,low,high);
if(kth<p)
quickSort(a,kth,low,p);
else if(kth>p)
quickSort(a,kth,p+1,high);
else
{
printf("% dth element is %d ",kth,a[p]);
return;
}
}
}
int partition(int a[],int low, int high)
{
int i,j,temp,p;
i=low-1;
j=high+1;
while(j!=0)
{
do
{
j=j-1;
}
while(a[j]>a[low]);
do
{
i=i+1;
}
while(a[i]<a[low]);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
{
break;
}
}
return j;
}
Write a c program to find kth element in an array without fully sorting the array
(hint: use quick sort )
#include<stdio.h>
#include<stdlib.h>
void quickSort(int a[], int kth,int low, int high);
int partition(int a[],int low, int high);
int main()
{
int *a,n,i,kth;
printf("enter the number of elements ");
scanf("%d",&n);
a=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
printf("enter element ");
scanf("%d",&a[i]);
}
printf("enter the k ");
scanf("%d",&kth);
if(kth<n)
quickSort(a,kth-1,0,n-1);
else
printf("does not exist ");
return 0;
}
void quickSort(int a[], int kth,int low, int high)
{
int p;
if(low<high)
{
p=partition(a,low,high);
if(kth<p)
quickSort(a,kth,low,p);
else if(kth>p)
quickSort(a,kth,p+1,high);
else
{
printf("% dth element is %d ",kth,a[p]);
return;
}
}
}
int partition(int a[],int low, int high)
{
int i,j,temp,p;
i=low-1;
j=high+1;
while(j!=0)
{
do
{
j=j-1;
}
while(a[j]>a[low]);
do
{
i=i+1;
}
while(a[i]<a[low]);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
{
break;
}
}
return j;
}
No comments:
Post a Comment