Searching and sorting algorithm question. Bob is still working at the law firm a

Question

Searching and sorting algorithm question.

Bob is still working at the law firm as a junior associate and is still having to look up client information in the files. Kate was promoted so Bob took the opportunity to re-re-organize the files and has again sorted them by last name. Bob has to find client files by last name. He does this by looking at the file in the middle of the filing cabinet. If its client name comes before the name of the client he is looking for in the alphabet he looks at the file in middle of the back half of the filing cabinet, if its client name comes after the name he is looking for he looks at the file in the middle of the front half of the filing cabinet and if the file is the one he is looking for (the names are the same) he takes it out. He repeats this process each time he looks at a file, making a mental note of the last two files he looks at so that he knows which section of the filing cabinet he is going to find the middle file in. If he gets to a point where he has looked at two files next to each other then he stops because the file is not in the cabinet (or the client doesnt exist). a) What algorithm is this? (1 mark) b) Bob sometimes has to put new files in the filing cabinet, or move old files to storage. When he puts new files in the cabinet he looks for where they go by following the same process described in (a) above. If he finds a file with the same client name he puts the new file next to it. Otherwise, if he ends up not finding a file with the same name, and has just looked at two files next to each other then he puts the new file in between them. When Bob puts a new file in the cabinet he makes room by simply pushing all the files behind it further into the file cabinet (with one push), when he removes a file he pulls the files behind it forward a bit (to keep things tidy). What is the O Notation running time of this process? (1 mark) c) Assume that we adapt Bobs insertion and removal algorithms briefly described in (b) to insert and remove elements of an array. What is the O notation running time of the insertion and removal algorithms? Briefly explain your answer. (3 marks) d) Partners at the law firm occasionally take out files themselves. When they do this the rarely put them back in the right place. Because of this Bob has to re-sort the filing cabinet every week. He cant decide whether to use selection sort or insertion sort to do this. Which of these two algorithms would you recommend and why? (1 mark)

Explanation / Answer

1) The example is a simple case of binary search

2 & 3) This method has two parts actually
    i) searching the location
    ii) shifting the files
i. Since we are using binary search, time complexity is O(log(n))
ii. During shifting in worst case happens when the file is located at the first location. In that case we need to shift all the remaining files a bit. So the time complexity is O(n)

And if we consider the whole method,complexity is O(log(n)) + O(n) = O(n)

4) In this problem, the list is partially sorted, because it is stated that one or two files are out of sync.
Insertion sort and Selection sort are very similar in the term that after n iterations, first n elemtens of the list are sorted. But the main advantage of Insertion sort is, it performs comparison only as much as needed

So applying selection sort on the partially sorted stack of files, in best case the complexity will go down to O(n)

I kept the answers simple and I love you like them, Let me know if you are still facing problems with the locgic. I shall be glad to help you.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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