Question

Given an array with data 3, 6, 4, 1, 5, 2, 6, 5, 3, 7, 4 using random select to find the 9 th smallest number (use the last element in each sequence as pivot). Show the intermediate steps (the result of each recursive step including the pivot, k’s value and grouping).

Answer 1

#include
#include
#include
#include
#define MAX 100
using namespace std;

// Function to display an array of given size
void displayArray(int array[], int left, int right)
{
cout<<" Array contents: ";
// Loops till end of the array
for(int x = left; x < right; x++)
cout< cout< }// End of function

// Function to swap two elements
void swapping(int *first, int *second)
{
// Swapping process
int temp = *first;
*first = *second;
*second = temp;
}// End of function

// I am considering the last element as pivot and moves all smaller element to left of it
// and greater elements to right
int createPartition(int array[], int left, int right)
{
int rightPos = array[right], leftPos = left;

// Loops from left to right parameter value
for (int c = left; c <= right - 1; c++)
{
// Checks if current index position of array value is less than right position value
if (array[c] <= rightPos)
{
// Call the function to swap
swapping(&array[leftPos], &array[c]);
// Increase the left position by one
leftPos++;
}// End of if condition
}// End of for loop

// Call the function to swap
swapping(&array[leftPos], &array[right]);

// Return left position
return leftPos;
}// End of function

// This function returns k'th smallest element in array[left .. right] using
int kthSmallest(int array[], int left, int right, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= right - left + 1)
{
// Partition the array around last element and get
// position of pivot element in sorted array
int pivot = createPartition(array, left, right);
cout<<"\n Pivot element "<

// If position is same as k
if (pivot - left == k - 1)
return array[pivot];

// If position is more, recur for left sub array
if (pivot - left > k - 1)
{
// Calls the function to display left partition
cout<<"\n Left ";
displayArray(array, left, pivot - 1);

// Calls the function to display right partition
cout<<"\n Right ";
displayArray(array, pivot, right);

return kthSmallest(array, left, pivot - 1, k);
}// End of if condition

// Else recur for right sub array
return kthSmallest(array, pivot + 1, right, k - pivot + left - 1);
}// End of if condition

// If k is more than number of elements in array
return INT_MAX;
}// End of function

// Function to create an array of given size
void createArray(int array[], int size)
{
for(int x = 0; x < size; x++)
array[x] = (rand() % 100) + 1;
}// End of function

// Driver program to test above methods
int main()
{
int num;
int kthElement;

// Use current time as seed for random generator
srand(time(0));

// Accepts the size of array
cout<<"\n Enter the size of the array (less than 100): ";
cin>>num;
// Declares an array of user entered size
int array[num];

// Calls the function to create an array
createArray(array, num);

// Calls the function to display array contents
displayArray(array, 0, num);

// Accepts kth value
cout<<"\n Enter the kth value to find Kth smallest number: ";
cin>>kthElement;

// Calls the function to find and display kth smallest number
cout <<"\n "< return 0;
}// End of main function

Sample Output 1:

Enter the size of the array (less than 100): 10
Array contents: 73, 90, 27, 63, 99, 17, 31, 85, 65, 84,

Enter the kth value to find Kth smallest number: 4

Pivot element 6
Left Array contents: 73, 27, 63, 17, 31,

Right Array contents: 84, 85, 90,

Pivot element 4
Left Array contents: 27, 63, 17,

Right Array contents: 65,

Pivot element 2
Pivot element 3
4'th smallest element is 63

Sample Output 2:

Enter the size of the array (less than 100): 30
Array contents: 10, 71, 58, 14, 27, 99, 81, 11, 24, 9, 60, 33, 27, 13, 55, 53, 48, 98, 48, 28, 2, 82, 41, 95, 92, 53, 60, 55, 49, 88,

Enter the kth value to find Kth smallest number: 9

Pivot element 25
Left Array contents: 10, 71, 58, 14, 27, 81, 11, 24, 9, 60, 33, 27, 13, 55, 53, 48, 48, 28, 2, 82, 41, 53, 60, 55,

Right Array contents: 88, 99, 95, 92,

Pivot element 14
Left Array contents: 10, 14, 27, 11, 24, 9, 33, 27, 13, 48, 48, 28, 2,

Right Array contents: 49, 60, 71, 58, 81, 82, 55, 53, 60, 55,

Pivot element 11
Left Array contents: 10, 14, 27, 11, 24, 9, 33, 27, 13, 28,

Right Array contents: 41, 48,

Pivot element 0
Pivot element 2
Pivot element 8
9'th smallest element is 27