C++ Program to Find kth Smallest Element in Array using Partitioning

«
»

C++ Program to find a Kth smallest element by the method of partitioning the array.

Problem Description

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

Problem Solution
advertisement

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.

Program/Source Code

C++ program to find kth smallest element by the method of partitioning the array.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#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 "<<i+1<<": ";
		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: "<<arr[kk];
 
	return 0;
}
Program Explanation

1. Take the input of the data set.
2. Take the input of the value of k.
3. Call Partition().
4. Inside Partition(), rearrange the array according to the pivot using CreatePartition().
5. Get the new index of the pivot as ‘pindex’ and compare it with (k-1).
6. If both the values are equal then return the value as a result to the main().
7. If pindex > k-1, recursively call Partition() for the part before the pivot value.
8. If pindex < k-1, recursively call Partition() for the part after the pivot value. 9. Inside main(), print the kth smallest element. 10. Exit.

Runtime Test Cases
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
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

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.