Question
In: Computer Science
What is the running time of Quicksort when the input array is sorted in ascending order?...
What is the running time of Quicksort when the input array is
sorted in ascending order? (please explain in detail)
Solutions
Expert Solution
Analysis of Time complexity of quick sort algorithm:
T(n) = T(k) + T(n-k-1) + 
(n)
Where k is the number of items less than pivot
n is number of items in array
The first two terms are included for the recursive quicksort
calls.
The last term is for the partition algorithm used in quick
sort.
Solution:
When the elements are already in sorted order, the smallest element
is present at the start of array and the largest element is present
at the end of array.
The worst case in the quick sort occurs when the algorithm selects
the smallest or largest item as pivot.
The last element here is the largest element.
So, the worst case occurs when the array is already sorted.
The worst case time is computed as shown below.
T(n) = T(0) + T(n-0-1) +
(n)
= T(n-1) +
(n)
=
(
)
Therefore, the running time of Quicksort when the
input array is sorted in ascending order is ().
venereology answered 1 year agoRelated Solutions
What is the running time of QUICKSORT on an array A of length n containing all...
What is the running time of QUICKSORT on an array A of length n
containing all the same values? What is the running time if A
contains distinct elements sorted in decreasing order? Explain your
answers in detail, referring to the source code for PARTITION and
QUICKSORT.
Following is the algorithm of Quicksort for sorting an array of integers in ascending order. Partition(numbers,...
Following is the algorithm of Quicksort for sorting an array of
integers in ascending order.
Partition(numbers, lowIndex, highIndex) {
midpoint = lowIndex + (highIndex - lowIndex) /
2
pivot = numbers[midpoint]
done = false
while (!done) {
while (numbers[lowIndex]
< pivot)
lowIndex++
while (pivot <
numbers[highIndex])
highIndex--
if (lowIndex >=
highIndex) {
done =
true
}
else {
temp =
numbers[lowIndex]
numbers[lowIndex]
= numbers[highIndex]
numbers[highIndex]
= temp
lowIndex++
highIndex--
}
}
return highIndex
}
Quicksort(numbers, lowIndex, highIndex) {
if (lowIndex...
Written in MIPS assembly language If given an array which is sorted in ascending order, as...
Written in MIPS assembly language
If given an array which is sorted in ascending order, as well as
its length and a target value. You are asked to find the index of
this target value in the array using binary search algorithm. Here
is an example: array 1, 4, 6, 8, 10, 12 length 6 target 8 2 In this
case, the returned result should be assigned to be 3, as array[3]
is equal to target. (Note: The target will...
1a .Write a program that perform insertion sort (ascending order) on an input array and print...
1a .Write a program that perform insertion sort (ascending
order) on an input array and print the total number of comparisons
that have been made. You can implement by using any programming
languages such as C/C++. For example, in the case of array B = [ 30
, 10 , 20 , 40 ], there are 4 needed comparisons to perform
insertion sort (30 vs 10, 20 vs 30, 20 vs 10, and 40 vs 30).
1b. Write a program...
in C++ Given two integer arrays sorted in the ascending order, code the function SortArrays to...
in C++
Given two integer arrays sorted in the ascending order, code the
function SortArrays to merge them into one array in the descending
order. You need to make sure if the values in the arrays are
changed, it will still work. (25 points)
#include <iostream>
using namespace std;
void SortArrays (int a[], int b[], int c[], int size);
void printArray(int m[], int length);
const int NUM = 5;
int main()
{
int arrA[NUM] = {-2, 31, 43, 55, 67};...
Given two integer arrays sorted in the ascending order, code the function SortArrays to merge them...
Given two integer arrays sorted in the ascending order, code the
function SortArrays to merge them into one array in the descending
order. You need to make sure if the values in the arrays are
changed, it will still work. (25 points) #include using namespace
std; void SortArrays (int a[], int b[], int c[], int size); void
printArray(int m[], int length); const int NUM = 5; int main() {
int arrA[NUM] = {-2, 31, 43, 55, 67}; int arrB[NUM] =...
Given two integer arrays sorted in the ascending order, code the function SortArrays to merge them...
Given two integer arrays sorted in the ascending order, code
the function SortArrays to merge them into one array in the
descending order. You need to make sure if the values in the arrays
are changed, it will still work. (25 points)
#include <iostream>
using namespace std;
void SortArrays (int a[], int b[], int c[], int size);
void printArray(int m[], int length);
const int NUM = 5;
int main()
{
int arrA[NUM] = {-2, 31, 43, 55, 67};
int arrB[NUM]...
Given two integer arrays sorted in the ascending order, code the function SortArrays to merge them...
Given two integer arrays sorted in the ascending order, code
the function SortArrays to merge them into one array in the
descending order. You need to make sure if the values in the arrays
are changed, it will still work. (25 points)
#include <iostream>
using namespace std;
void SortArrays (int a[], int b[], int c[], int size);
void printArray(int m[], int length);
const int NUM = 5;
int main()
{
int arrA[NUM] = {-2, 31, 43, 55, 67};
int arrB[NUM]...
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array...
Given an integer array sorted in non-decreasing order, there is
exactly one integer in the array that occurs more than 25% of the
time. Return that integer.
Input:
arr = [1,2,2,6,6,6,6,7,10]
Output:
Write down an algorithm in pseudo-code whose running time where input is an array whose length...
Write down an algorithm in pseudo-code whose running time where
input is an array whose length defines the problem size. Take the
cost of execution of each line of the algorithm as 1.
Make comment about the following paragraph:
“You are given two independent
algorithms and whose running time complexities are and ,
respectively. If we add a new line to our algorithm in which it
calls the algorithm then the running time complexity of the
modified algorithm becomes ”.
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- What are the basic differences between proprietary and public companies? there are 5 basic differences between...
- Write a C++ program to read in various types of test questions (multiple choice and True/False)...
- Write a C program that accepts a port number as a command line argument, and starts...
- Given that labor is a resource that needs to be used efficiently, what responsibility do you...
- When you develop a research project, you need to have a reliable and valid method of...
- Suppose you have a list containing exactly three integer numbers. Each number could be positive, negative,...
- Explain the relation between muscles, ATP energy, and the calcium ion
ADVERTISEMENT