Answered step by step
Verified Expert Solution
Question
1 Approved Answer
A bubble (swap) sorter is used to sort 100,000 words for an English language dictionary application. a) Show that the number of swaps required
A bubble (swap) sorter is used to sort 100,000 words for an English language dictionary application. a) Show that the number of swaps required to sort N words in a dictionary is approximately N. [1 mark] b) A student measures that a swap operation takes 0.01 ms on an old piece of hardware. Ignoring all other computing overheads, exactly how long will it take to sort the dictionary into alphabetical order? [1 mark] c) How many comparison operations would it take on average to locate a word in a sorted dictionary using linear search? [1 mark] d) Explain whether the answer for part (c) would be different if the dictionary was unsorted? [1 mark] e) How many comparison operations would it take to locate a word in the sorted dictionary using a binary search? [3 mark] f) Explain, with the aid of diagrams as appropriate, how a sorted list of words could be organised into a binary search tree.
Step by Step Solution
★★★★★
3.39 Rating (149 Votes )
There are 3 Steps involved in it
Step: 1
a In a bubble sortthe number of swaps required in each pass is approximately equal to the number of elements out of orderIn the first passthe largest element is moved to the end of the listleaving N1 ...Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started