申論題

8. (3 points) A randomized linked list sorting algorithm works as follows. We want to build a linked list
in which the keys are in increasing order. That is, every node has a smaller key than its successor in
the list. For ease of discussion we assume that the keys are distinct in integers from 1 to n. The algorithn
randomly picks a key from the rem maining keys, and inserts it into the list. This pro
keys are inserted. The inserted key k will skip those at the beginning of the list that are smaller than
ocess repeats until all
it, and will stop at the first key p that are greater than it. We then insert the key k  before p. To ensure
that all keys will stop we assumne that initially the list has only one key, n + 1. After we insert all keys
we will have a sorted linked list from 1 to n + 1.
1. Every inserted key will stop exactly once.
 2. The smallest key 1 will not skip any keys.
3. The largest key n will always skip n–1 keys.
 4. The expected number of keys that the key i will skip is Ω(i).