Code:
#include iostream
using namespace std;
// Swapping two values.
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Partitioning the array on the basis of values at high as pivot value.
int CreatePartition(int a[], int low, int high)
{
int pivot, index, i;
index = low;
pivot = high;
// Getting index of pivot.
for(i=low; i < high; i++)
{
if(a[i] < a[pivot])
{
swap(&a[i], &a[index]);
index++;
}
}
// Swapping value at high and at the index obtained.
swap(&a[pivot], &a[index]);
return index;
}
// Implementing Partition.
int Partition(int a[], int low, int high, int k)
{
int pindex;
if(low < high)
{
// Partitioning array using last element as a pivot.
// Recursively implementing partitioning in the direction to place the pivot at (k-1)th pivot.
pindex = CreatePartition(a, low, high);
if(pindex == k-1)
return k-1;
else if(pindex > k-1)
Partition(a, low, pindex-1, k);
else
Partition(a, pindex+1, high, k);
}
}
int main()
{
int n, i, k, kk;
cout<<"\nEnter the number of data element: ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<
cin>>arr[i];
}
cout<<"\nEnter the k for the kth smallest element: ";
cin>>k;
kk = Partition(arr, 0, n-1, k);
// Printing the result.
cout<<"\nThe kth smallest element: "<
return 0;
}
Output:
Case 1:
Enter the number of data element: 10
Enter element 1: 9
Enter element 2: 4
Enter element 3: 0
Enter element 4: 3
Enter element 5: 7
Enter element 6: 8
Enter element 7: 1
Enter element 8: 5
Enter element 9: 6
Enter element 10: 2
Enter the k for the kth smallest element: 4
The kth smallest element: 3
More C++ Programs:
