If you were to get these questions on a test and could not use a computer to ans
ID: 3850252 • Letter: I
Question
If you were to get these questions on a test and could not use a computer to answer this question, only pen and paper.
How would you answer them? Please explain in detail and with step-by-step on how to approach questions like these :)
An algorithm, that sorts a sequence of elements, can be illustrated as below: CH, B, G, A, E, F, C, DJ [B, H, G, A, E, F, C, DJ CB, G, H, A, E, F, C, DJ CA, B, G, H, E, F, C, D] CA, B, E, G, H, F, C, D] CA, B, E, F, G, H, C, D [A, B, C, E, F, G, H, DJ CA, B, C, D, E, F, G, H] CA, B, C, D, E, F, G, H] a Create a method sort that accepts an array of character strings, and sorts them according to the given algorithm. b) Let n denote the number of elements to be sorted. Determine in such a case the time complexity for the algorithm in terms of the number of comparisons -both the best case and the worst case. Categorize the corresponding complexity functions: to which o-set do they belong?Explanation / Answer
The idea is to look at the algorithm swaps , how the elements are getting sorted from the algorithm trace it looks that every time an element is inserted into the sorted sequen
this sort algorithm is Insertion Sort
void sort(int array[])
{
for (int i=1; i<array.length;i++)
{
int key = array[i];
int j = i-1;
while (j>=0 && array[j] > key)
{
array[j+1] = arr[j];
j = j-1;
}
array[j+1] = key;
}
}
B) Time complexity of the algortihm is O(n^2) in case of worst case and O(n) in case of best case,when the elements are sorted.
Cheers:)