C++ Programming Code Examples C++ > Arrays and Matrices Code Examples Program to Find kth Smallest Element by the Method of Partitioning the Array Program to Find kth Smallest Element by the Method of Partitioning the Array 1. Implement partitioning to find the Kth smallest number from a dataset of n element. 2. The time complexity of this algorithm is O(n*log(n)). 1. Take the input of the data set. 2. Use the partition algorithm. 3. As we place the pivot at the (k-1)th index it will be the kth smallest number. 3. Exit. #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, x; index = low; pivot = high; // Getting index of pivot. for(x=low; x < high; x++) { if(a[x] < a[pivot]) { swap(&a[x], &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, x, k, kk; cout<<"\nEnter the number of data element: "; cin>>n; int arr[n]; for(x = 0; x < n; x++) { cout<<"Enter element "<<x+1<<": "; cin>>arr[x]; } 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: "<<arr[kk]; return 0; }