Already have an account? Get multiple benefits of using own account!
Login in your account..!
Remember me
Don't have an account? Create your account in less than a minutes,
Forgot password? how can I recover my password now!
Enter right registered email to receive password!
Q. Explain the insertion sort with a proper algorithm. What is the complication of insertion sort in the worst case?
Ans:
Insertion Sort technique: One of the easiest sorting algorithms is the insertion sort.
Insertion sort comprises of n - 1 passes. For pass p = 2 through n, insertion sort assures that the elements in the positions 1 through p are in sorted order. Insertion sort makes use of the fact those elements in positions 1 through p - 1 are already known in the sorted order.
Void insertion_sort( input_type a[ ], unsigned int n )
{
unsigned int j, p;
input_type tmp;
a[0] = MIN_DATA; /* sentinel */
for( p=2; p <= n; p++ )
tmp = a[p];
for( j = p; tmp < a[j-1]; j-- )
a[j] = a[j-1];
a[j] = tmp;
}
Because of the nested loops present, each of which can take n iterations, insertion sort is O(n2). Furthermore, this bound is tight, because input in reverse order can actually obtain this bound. A precise calculation shows that the test at line 4 can be executed at most of the p times for each value of p. By summing over all p gives a total of (n(n-1))/2 = O(n2).
Q. What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine. A n
1. Show the effect of each of the following operations on queue q. Assume that y (type Character) contains the character ‘&’. What are the final values of x and success (type boole
Explain the bubble sort algorithm. Answer This algorithm is used for sorting a list. It makes use of a temporary variable for swapping. It compares two numbers at an insta
As we have seen, as the traversal mechanisms were intrinsically recursive, the implementation was also easy through a recursive procedure. Though, in the case of a non-recursive me
design algorithm and flow chart that computes the absolute difference of two values x and y
Stacks are often used in evaluation of arithmetic expressions. An arithmetic expression contains operands & operators. Polish notations are evaluated through stacks. Conversions of
Q. Explain the basic concept of the primitive data structures. Ans. The concept of P r i m i t i ve Data
Demonstrate that Dijkstra's algorithm does not necessarily work if some of the costs are negative by finding a digraph with negative costs (but no negative cost dicircuits) for whi
In this example, suppose the statements are simple unless illustrious otherwise. if-then-else statements if (cond) { sequence of statements 1 } else { sequence of st
Q. Convert the given infix expression into the postfix expression (also Show the steps) A ∗ (B + D)/ E - F(G + H / k ) Ans. Steps showing Infix to Post fix
Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!
whatsapp: +1-415-670-9521
Phone: +1-415-670-9521
Email: [email protected]
All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd