Given an n-element unsorted array A of n integers and an integer k, describe and implement a recursive algorithm for rearranging the elements in A so that all elements less than or equal to k come before any elements larger than k. What is the running time of your algorithm? Please prove the running time in the comments . in c++ please
Program screenshots:
Sample output:
Code to copy:
// Include the required header files.
#include <iostream>
// Use the standard namespace.
using namespace std;
// Define the function to rearrange the elements.
void rearrange(int A[], int k, int start, int end)
{
// Return if the starting index is equal
// to the last index.
if(start == end)
{
return;
}
// Otherwise, do the following.
else
{
// Swap the element at A[start] with the
// element at A[end] if the value of A[start]
// is greater than k.
if(A[start] > k)
{
int temp = A[start];
A[start] = A[end];
A[end] = temp;
// Decrement the value of end by 1
// and call the function recursively.
rearrange(A, k, start, end-1);
}
// Otherwise, increment the value of start
// by 1 and call the function recursively.
else
{
rearrange(A, k, start+1, end);
}
}
}
// Define the main() function.
int main()
{
// Declare the required variables.
int A[] = {100,-1, 4,3,2,0,23,34,6,7,102};
int n = sizeof(A)/sizeof(A[0]);
int k = 20;
cout << "k = " << k << endl;
cout << "The original array is as follows:" << endl;
// Start the loop to print the original array.
for(int i=0; i<n; i++)
{
cout << A[i] << " ";
}
// Call the function to rearrange the elements.
rearrange(A, k, 0, n-1);
cout << endl;
cout << "\nThe modified array is as follows:" << endl;
// Start the loop to print the modified array.
for(int i=0; i<n; i++)
{
cout << A[i] << " ";
}
// Return 0 and exit the program.
return 0;
}
The running time of the above code/algorithm is as follows:
Hence, the total running time of the algorithm is O(n) + C.
Given an n-element unsorted array A of n integers and an integer k, describe and implement...
Design and implement a Θ(n) algorithm that will simultaneously find the largest and second-largest elements (integers) in an array. Note that the second largest element should be distinctly smaller than the largest element. You should also adhere to the following restrictions. (1) You should traverse through the array ONLY ONCE. (2) The array could have both positive and negative elements. So, you should NOT initialize any temporary variables to very small negative values as part of your algorithm. (3) You...
Given as input an array A of n positive integers and another positive integer x, describe an O(nlogn)-time algorithm that determines whether or not there exist two elements Ai and AONn the array A such that is exactly x.
Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity? Group of answer choices nsertion Sort with time complexity O(kn) Heap Sort with time complexity O(nLogk) Quick Sort with time complexity O(kLogk) Merge Sort with time...
In Java, Implement a class MyArray as defined below, to store an array of integers (int). Many of its methods will be implemented using the principle of recursion. Users can create an object by default, in which case, the array should contain enough space to store 10 integer values. Obviously, the user can specify the size of the array s/he requires. Users may choose the third way of creating an object of type MyArray by making a copy of another...
We are given an array A holding n integers, for some large n. The array is sorted, and the values in A range from -2147483648 to 2147483647, evenly distributed. Give Θ expressions for the following tasks: A. Running the insertion sort algorithm on the array A: B. Running the selection sort algorithm on the array A: C. Performing binary search for integer k which is not in A: D. Performing interpolation search for integer k not in A:
The input is an array of N integers ( sorted ) and an integer X. The algorithm returns true if X is in the array and false if X is not in the array. Describe an algorithm that solves the problem with a worst case of O(log N) time.
Design an algorithm for the following description. Solution can
be done in pseudo-code or steps of the algorithm.
Describe and analyze an algorithm that takes an unsorted array A of n integers (in an unbounded range) and an integer k, and divides A into k equal-sized groups, such that the integers in the first group are lower than the integers in the second group, and the integers in the second group are lower than the integers in the third group,...
2. Here is a sorting algorithm that I like to use. Given an unsorted list of size n, let Xx represent the data in location k of the unsorted list. Compare xi to X2 and switch if necessary so that they are in sorted order, smallest first. Compare Xn-1 and Xn and switch if necessary so that they are in sorted order, smallest first. • Compare x3 with its left neighbors, switching if necessary so that the 3 first entries...
using MIPS MARS sort an array of n integers and print both the sorted and unsorted array. n should be greater than or equal to 10 and entered by the user. Reminder make sure to use MIPS MARS only
I need help In the lecture you got acquainted with the median algorithm, which calculates the median of an unsorted array with n∈N elements in O (n). But the algorithm can actually do much more: it is not limited to finding only the median, but can generally find the ith element with 0≤i <n. Implement this generic version of the median algorithm by creating a class selector in the ads.set2.select package and implementing the following method: /** * Returns the...