Implement the algorithm kSmall as a C++ function. Use the first value of the arr
ID: 2876200 • Letter: I
Question
Implement the algorithm kSmall as a C++ function. Use the first value of the array as the pivot.
Use the main file that tests the class with data from a text file. Your code should work for any given file that has integers enumerated in a file (one value per line).
Use the Doxygen to generate documentation for the code you developed.
**I think they want this done with recursion? Let me know if you need more Info. As I cannot seem to find reference to the algorithm kSmall...
The main file is as follows:
The text file is:
Explanation / Answer
Ans)
Method -1:
A Simple Solution is to sort the given array using a O(nlogn) sorting algorithm like Merge Sort, Heap Sort, etc and return the element at index k-1 in the sorted array. Time Complexity of this solution is O(nLogn).
// Simple C++ program to find k'th smallest element
#include<iostream>
#include<algorithm>
using namespace std;
// Function to return k'th smallest element in a given array
int kthSmallest(int arr[], int n, int k)
{
// Sort the given array
sort(arr, arr+n);
// Return k'th element in the sorted array
return arr[k-1];
}
// Driver program to test above methods
int main()
{
int arr[] = {12, 3, 5, 7, 19};
int n = sizeof(arr)/sizeof(arr[0]), k = 2;
cout << "K'th smallest element is " << kthSmallest(arr, n, k);
return 0;
}
Method 2:
We can find k’th smallest element in time complexity better than O(nLogn). A simple optomization is to create a Min Heap of the given n elements and call extractMin() k times.
The following is C++ implementation of above method.
// A C++ program to find k'th smallest element using min heap
#include<iostream>
#include<climits>
using namespace std;
// Prototype of a utility function to swap two integers
void swap(int *x, int *y);
// A class for Min Heap
class MinHeap
{
int *harr; // pointer to array of elements in heap
int capacity; // maximum possible size of min heap
int heap_size; // Current number of elements in min heap
public:
MinHeap(int a[], int size); // Constructor
void MinHeapify(int i); //To minheapify subtree rooted with index i
int parent(int i) { return (i-1)/2; }
int left(int i) { return (2*i + 1); }
int right(int i) { return (2*i + 2); }
int extractMin(); // extracts root (minimum) element
int getMin() { return harr[0]; } // Returns minimum
};
MinHeap::MinHeap(int a[], int size)
{
heap_size = size;
harr = a; // store address of array
int i = (heap_size - 1)/2;
while (i >= 0)
{
MinHeapify(i);
i--;
}
}
// Method to remove minimum element (or root) from min heap
int MinHeap::extractMin()
{
if (heap_size == 0)
return INT_MAX;
// Store the minimum vakue.
int root = harr[0];
// If there are more than 1 items, move the last item to root
// and call heapify.
if (heap_size > 1)
{
harr[0] = harr[heap_size-1];
MinHeapify(0);
}
heap_size--;
return root;
}
// A recursive method to heapify a subtree with root at given index
// This method assumes that the subtrees are already heapified
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}
// A utility function to swap two elements
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// Function to return k'th smallest element in a given array
int kthSmallest(int arr[], int n, int k)
{
// Build a heap of n elements: O(n) time
MinHeap mh(arr, n);
// Do extract min (k-1) times
for (int i=0; i<k-1; i++)
mh.extractMin();
// Return root
return mh.getMin();
}
// Driver program to test above methods
int main()
{
int arr[] = {12, 3, 5, 7, 19};
int n = sizeof(arr)/sizeof(arr[0]), k = 2;
cout << "K'th smallest element is " << kthSmallest(arr, n, k);
return 0;
}
Output:
I think these assumptions can make your answer
I too cannot predict the same way
I will work on it, untill then please go through it
// A C++ program to find k'th smallest element using min heap
#include<iostream>
#include<climits>
using namespace std;
// Prototype of a utility function to swap two integers
void swap(int *x, int *y);
// A class for Min Heap
class MinHeap
{
int *harr; // pointer to array of elements in heap
int capacity; // maximum possible size of min heap
int heap_size; // Current number of elements in min heap
public:
MinHeap(int a[], int size); // Constructor
void MinHeapify(int i); //To minheapify subtree rooted with index i
int parent(int i) { return (i-1)/2; }
int left(int i) { return (2*i + 1); }
int right(int i) { return (2*i + 2); }
int extractMin(); // extracts root (minimum) element
int getMin() { return harr[0]; } // Returns minimum
};
MinHeap::MinHeap(int a[], int size)
{
heap_size = size;
harr = a; // store address of array
int i = (heap_size - 1)/2;
while (i >= 0)
{
MinHeapify(i);
i--;
}
}
// Method to remove minimum element (or root) from min heap
int MinHeap::extractMin()
{
if (heap_size == 0)
return INT_MAX;
// Store the minimum vakue.
int root = harr[0];
// If there are more than 1 items, move the last item to root
// and call heapify.
if (heap_size > 1)
{
harr[0] = harr[heap_size-1];
MinHeapify(0);
}
heap_size--;
return root;
}
// A recursive method to heapify a subtree with root at given index
// This method assumes that the subtrees are already heapified
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}
// A utility function to swap two elements
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// Function to return k'th smallest element in a given array
int kthSmallest(int arr[], int n, int k)
{
// Build a heap of n elements: O(n) time
MinHeap mh(arr, n);
// Do extract min (k-1) times
for (int i=0; i<k-1; i++)
mh.extractMin();
// Return root
return mh.getMin();
}
// Driver program to test above methods
int main()
{
int arr[] = {12, 3, 5, 7, 19};
int n = sizeof(arr)/sizeof(arr[0]), k = 2;
cout << "K'th smallest element is " << kthSmallest(arr, n, k);
return 0;
}