6. Assume the following list: 7, 28, 31, 40, 5, 20. The first four keys are in o

Question

6. Assume the following list: 7, 28, 31, 40, 5, 20. The first four keys are in order. to move 5 to its proper position, using insertion sort as described in this chapter, exactly how many key comparisons are executed?

8. Recall the insertions sort algorithm as discussed in this chapter. Assume the following list of keys: 18, 8, 11, 9, 15, 20, 32, 61, 22, 48, 75, 83, 35, 3.

10. Suppose that you have the following Vector oberject list:

     list = ["one", "two", "three", "four"];

    What are the elements of list after the following statements execute?

     list.addElement("Five");

     list.insertElementAt("six", 1);

Explanation / Answer

Given List :- [7, 28, 31, 40, 5, 20]

since first four keys are inorder(basically already sorted ) and now we are adding one more key 5 into the list so that including key 5 , list remains inorder.

in insertion sort we assume that we have already a sorted araay and we add key to it and put it in it's right position. so we start comparing key(element) with the given sorted araay.

so in our case 5 is compared with 40 , 31 , 28 , 7 after that we can put it in it's right position , now if we have a key 9 then no of comparision are 30( with 40, 31, 28)

so no of comparision for key 5 = 4

[18, 8, 11, 9, 15, 20, 32, 61, 22, 48, 75, 83, 35, 3]

sorted array [18] key = 8 [8, 18, (rest is same)]

sorted array [8, 18] key = 11 [8, 11, 18, .. ]

[8, 11, 18] key=9 [8, 9, 11, 18, ...]

[8, 9, 11, 18] key=15 [8, 9, 11, 15, 18, ...]

[8, 9, 11, 15, 18, 20, . . .]

[8, 9, 11, 15, 18, 20, 32, ...]

[8, 9, 11, 15, 18, 20, 32, 61, 22, 48, 75, 83, 35, 3]

[8, 9, 11, 15, 18, 20, 22, 32, 61, 48, 75, 83, 35, 3]

[8, 9, 11, 15, 18, 20, 22, 32, 48, 61, 75, 83, 35, 3]

[8, 9, 11, 15, 18, 20, 22, 32, 48, 61, 75, 83, 35, 3 ]

[8, 9, 11, 15, 18, 20, 22, 32, 48, 61, 75, 83, 35, 3 ]

[8, 9, 11, 15, 18, 20, 22, 32, 35, 48, 61, 75, 83, 3 ]

[3, 8, 9, 11, 15, 18, 20, 22, 32, 35, 48, 61, 75, 83 ]

list = ["one", "two", "three", "four"] key="Five"

key is less than all other values of list so it will be added at starting of list

list = ["Five", "one", "two", "three" , "four"]

in the next we are inserting at specified position 1

so "six" will be added at list[1]

list = ["Five", "six", "one", "two", "three" , "four"]

string comparision:

"one" > "Five" since ascii values are compared during string comparision

i hope this helps .... if still you have any doubt ...then comment on this ... :D

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

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