Question

In: Computer Science

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

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

Solutions

Expert Solution

#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


Related Solutions

trace by using quicksort on the array : 4 6 5 3 2 7 1 using...
trace by using quicksort on the array : 4 6 5 3 2 7 1 using 7 as the pivot
Using the same data… 2 3 4 4 4 6 6 6 7 8 8 9...
Using the same data… 2 3 4 4 4 6 6 6 7 8 8 9 10 10 11 12 16 16 28 46 (d) [5 pts] Determine the 5# summary. (e) Determine the lower and upper fence to determine if there are any outliers. (f) Draw and carefully label a modified boxplot for this data. (g) What is the shape of the distribution (symmetric, skewed left, or skewed right). Explain.
x 2 8 5 9 4 3 9 6 7 8 y 3 6 5 7...
x 2 8 5 9 4 3 9 6 7 8 y 3 6 5 7 9 7 4 6 9 9 -5.48x + 0.17 5.48x + 0.17 -0.17x + 5.48 0.17x + 5.48
3, 7, 8, 5, 6, 4, 9, 10, 7, 8, 6, 5 Using the previous question...
3, 7, 8, 5, 6, 4, 9, 10, 7, 8, 6, 5 Using the previous question 's scores, If three points were added to every score in this distribution, what would be the new mean? If three points were added to every score in this distribution, what would be the new standard deviation. Remember, you have already calculated population standard deviation in a previous problem. This problem requires two answers.
Given the matrix 7 7 -4 12 -5 A = 9 10 2 6 13 8 11 15 4 1 3. a. Sort each column and store the result in an array B.
Given the matrix a. Sort each column and store the result in an array B.b. Sort each row and store the result in an array C.c. Add each column and store the result in an array D.d. Add each row and store the result in an array E.  
Find regression line for the data X 0   1   2   3    4   5   6   7  8          &nbsp
Find regression line for the data X 0   1   2   3    4   5   6   7  8               [3 MARKS] Y 11 21 31 41 51 61 71 81 91 b. X  0   2   4   6   8  10                            [3 MARKS]       Y  12 15 17 18 20 22
Considering the following time series data: Week 1 2 3 4 5 6 7 8 9...
Considering the following time series data: Week 1 2 3 4 5 6 7 8 9 10 Sales 8 11 14 19 16 10 8 12 14 16 Compute the naïve forecast and the three-week Moving Average and evaluate the forecast accuracy considering the Mean Absolute Error (MAE), Mean Squared Error (MSE) and the Mean Absolute Percentage Error (MAPE) for each of these two predictions. Compare both of them and determine which is the best model
1.Consider the program: .data myArray: .word 1, 2, 3, 4, 5, 6, 7, 8, 9, 10...
1.Consider the program: .data myArray: .word 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 .text la $s0, myArray li $s1, 0 loop: sll $t0, $s1, 2 add $t0, $t0, $s0 lw $s2, 0($t0) lw $s3, 4($t0) add $s2, $s2, $s3 sw $s2, 0($t0) addi $s1, $s1, 1 slti $t1, $s1, 9 bne $t1, $zero, loop .end Explain what does this program do? How is the data bound from the .data segment to the base address register $s0? What...
Step 2 Data Set A x 1 2 3 4 5 6 7 y 7 7...
Step 2 Data Set A x 1 2 3 4 5 6 7 y 7 7 7 9 9 9 10 Data Set B x 1 2 3 4 5 6 7 8 9 10 11 y 4 6 6 6 8 9 9 9 10 10 10 Step 2 Find the equation for the least-squares line, and graph the line on the scatter plot. Find the sample correlation coefficient r and the coefficient of determination r2. Is r significant?...
ID X Y 1 2 3 2 3 6 3 4 6 4 5 7 5...
ID X Y 1 2 3 2 3 6 3 4 6 4 5 7 5 8 7 6 5 7 7 6 7 8 8 8 9 7 8 10 12 11 Test the significance of the correlation coefficient. Then use math test scores (X) to predict physics test scores (Y).  Do the following: Create a scatterplot of X and Y. Write the regression equation and interpret the regression coefficients (i.e., intercept and slope). Predict the physics score for each....
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT