Finding k th element by quick sort

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;
}    

No comments:

Post a Comment