java Explain why the insertion-sort algorithm has worst-case runtime cost of 0(n

Question

java

Explain why the insertion-sort algorithm has worst-case runtime cost of 0(n^2) to sort n items. Describe the algorithm to search for an item with given key, in a hash table that uses open addressing with double hashing. Consider a class MyList Implementation that keeps a doubly linked list with header and trailer sentinel nodes (referenced by instance variables of the list implementation called header and trailer). Assume that the Node class has the usual getter and setter methods. Suppose n is a Node within the list (not one of the sentinels). Write the sequence of Java statements that would be used within MyListlmplementation, in order to remove the Node n from the list. [You can use assignments to instance variables and you can call methods of the Node class, but do not call methods of the List ADT itself.] Write an explanation for a beginning programmer, to teach them the difference between the following two ways of determining the order between items: using a Comparator and a Comparable. An Iterator object is used in data structures, to allow the user to access the items in a collection one-by-one. Give instructions that teach someone how to define an Iterator for a collection based on linked nodes. In particular, you need to indicate any methods that the Iterator must have.

Explanation / Answer

Q1>The worst case of insertion sort occurs when the array is sorted in decreasing order.In insertion sort,call to insert fucntion will result in every element to slide over if the number being inserted is less than every element to its left. Hence, if every element is less than every element to its left, the running time of insertion sort is O(n2).

================================================================================

Q2>

Step 1:Let i = hash(key)

Step 2:If the data[i]==item:

then item is found at location i and go to Step 4

Step 3:Else:

i = (i+hash2(key)) % SIZE

and again jump to Step 2

Step 4:Exit

====================================================================

Q.4

Comparable VsComparator.

Ans:1)When class implements Comparable interface it gives compareTo() method while

Comparator provides compare() method to sort elements.

2)in Comparable ,we can sort on the basis of single element while in Comparator we can sort on the basis of multiple elements

3)Comparable changes actual class.While Comparator doesn't affect the original class.

4)Comparable is in java.lang package and Comparator is found in java.util package.

=======================================================================

Q5

Comparator provides compare() method to sort elements.

2)in Comparable ,we can sort on the basis of single element while in Comparator we can sort on the basis of multiple elements

3)Comparable changes actual class.While Comparator doesn't affect the original class.

4)Comparable is in java.lang package and Comparator is found in java.util package.

=======================================================================

Q5

  LinkedList list = new LinkedList();//create object of list class  Iterator x = list.listIterator(1);//set iterator to any index.  

  //run loop till it points to next  while (x.hasNext())   {     System.out.println(x.next());//access data   }  

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.