A bubble (swap) sorter is used to sort 100,000 words for an English language dictionary application....

Transcribed Image Text:

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. 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.

Answer rating: 100% (QA)

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 ... View the full answer