full transcript

## Unscramble the Blue Letters

You work at the college liabrry. You're in the middle of a qiuet atrnofeon when suddenly a shipment of 1,280 different books arrives. The books have been dropped of in one long straight line, but they're all out of order, and the automatic sorting system is broken. To make meratts worse, classes start tomorrow, which means that first thing in the mrinnog, students will show up in droves looking for these books. How can you get them all sorted in time? One way would be to sratt at one end of the line with the first pair of bokos. If the first two books are in order, then leave them as they are. Otherwise, swap them. Then, look at the second and third books, repeat the process, and continue until you reach the end of the line. At some point, you'll come across the book that should be last, and keep swapping it with every subsequent book, mnviog it down the line until it reaches the end where it benolgs. Then, start from the beginning and repeat the process to get the second to last book in its proper place, and keep going until all books are sretod. This apacrpoh is called Bubble Sort. It's simple but slow. You'd make 1,279 comparisons in the first round, then 1,278, and so on, adding up to 818,560 comparisons. If each took just one second, the process would take over nine days. A second strategy would be to start by sorting just the first two books. Then, take the third book and compare it with the book in the second spot. If it belongs before the second book, swap them, then compare it with the book in the first spot, and swap again if needed. Now you've sorted the first three books. Keep adding one book at a time to the sorted sub-line, comparing and swapping the new book with the one before it until it's correctly placed among the books sorted so far. This is called Insertion Sort. Unlike bbblue Sort, it usually doesn't require comparing every pair of books. On average, we'd expect to only need to compare each book to half of the books that came before it. In that case, the total number of comparisons would be 409,280, taking almost five days. You're still doing way too many comparisons. Here's a better idea. First, pick a random book. Call it the partition and compare it to every other book. Then, divide the line by placing all the books that come before the potariitn on its left and all the ones that come after it on its right. You've just saved ldaos of time by not having to compare any of the books on the left to any of the ones on the right ever again. Now, looking only at the books on the left, you can again pick a random partition book and separate those books that come before it from those that come after it. You can keep cerntiag sub-partitions like this until you have a bunch of small sub-lines, each of which you'd sort quickly using another strategy, like Insertion Sort. Each round of partitioning reuieqrs about 1,280 comparisons. If your poiianrtts are pretty balanced, dividing the books into 128 sub-lines of ten would take about seven rounds, or 8,960 snoecds. sonitrg these sub-lines would add about 22 seconds each. All in all, this mthoed known as QuickSort could sort the books in under three and a half hours. But there's a catch. Your partitions could end up lopsided, saving no time at all. Luckily, this rarely happens. That's why QuickSort is one of the most enifcieft strategies used by programmers today. They use it for things like sorting items in an online store by price, or creating a list of all the gas stations close to a given lacotion sorted by daictnse. In your case, you're done quick sorting with time to spare. Just another high-stakes day in the library.

## Open Cloze

You work at the college _______. You're in the middle of a _____ _________ when suddenly a shipment of 1,280 different books arrives. The books have been dropped of in one long straight line, but they're all out of order, and the automatic sorting system is broken. To make _______ worse, classes start tomorrow, which means that first thing in the _______, students will show up in droves looking for these books. How can you get them all sorted in time? One way would be to _____ at one end of the line with the first pair of _____. If the first two books are in order, then leave them as they are. Otherwise, swap them. Then, look at the second and third books, repeat the process, and continue until you reach the end of the line. At some point, you'll come across the book that should be last, and keep swapping it with every subsequent book, ______ it down the line until it reaches the end where it _______. Then, start from the beginning and repeat the process to get the second to last book in its proper place, and keep going until all books are ______. This ________ is called Bubble Sort. It's simple but slow. You'd make 1,279 comparisons in the first round, then 1,278, and so on, adding up to 818,560 comparisons. If each took just one second, the process would take over nine days. A second strategy would be to start by sorting just the first two books. Then, take the third book and compare it with the book in the second spot. If it belongs before the second book, swap them, then compare it with the book in the first spot, and swap again if needed. Now you've sorted the first three books. Keep adding one book at a time to the sorted sub-line, comparing and swapping the new book with the one before it until it's correctly placed among the books sorted so far. This is called Insertion Sort. Unlike ______ Sort, it usually doesn't require comparing every pair of books. On average, we'd expect to only need to compare each book to half of the books that came before it. In that case, the total number of comparisons would be 409,280, taking almost five days. You're still doing way too many comparisons. Here's a better idea. First, pick a random book. Call it the partition and compare it to every other book. Then, divide the line by placing all the books that come before the _________ on its left and all the ones that come after it on its right. You've just saved _____ of time by not having to compare any of the books on the left to any of the ones on the right ever again. Now, looking only at the books on the left, you can again pick a random partition book and separate those books that come before it from those that come after it. You can keep ________ sub-partitions like this until you have a bunch of small sub-lines, each of which you'd sort quickly using another strategy, like Insertion Sort. Each round of partitioning ________ about 1,280 comparisons. If your __________ are pretty balanced, dividing the books into 128 sub-lines of ten would take about seven rounds, or 8,960 _______. _______ these sub-lines would add about 22 seconds each. All in all, this ______ known as QuickSort could sort the books in under three and a half hours. But there's a catch. Your partitions could end up lopsided, saving no time at all. Luckily, this rarely happens. That's why QuickSort is one of the most _________ strategies used by programmers today. They use it for things like sorting items in an online store by price, or creating a list of all the gas stations close to a given ________ sorted by ________. In your case, you're done quick sorting with time to spare. Just another high-stakes day in the library.

1. afternoon
2. books
3. partitions
4. seconds
5. method
6. distance
7. approach
8. belongs
9. creating
10. requires
11. bubble
12. start
13. matters
14. location
15. sorting
16. partition
17. morning
18. moving
19. sorted
20. library
22. efficient
23. quiet

## Original Text

You work at the college library. You're in the middle of a quiet afternoon when suddenly a shipment of 1,280 different books arrives. The books have been dropped of in one long straight line, but they're all out of order, and the automatic sorting system is broken. To make matters worse, classes start tomorrow, which means that first thing in the morning, students will show up in droves looking for these books. How can you get them all sorted in time? One way would be to start at one end of the line with the first pair of books. If the first two books are in order, then leave them as they are. Otherwise, swap them. Then, look at the second and third books, repeat the process, and continue until you reach the end of the line. At some point, you'll come across the book that should be last, and keep swapping it with every subsequent book, moving it down the line until it reaches the end where it belongs. Then, start from the beginning and repeat the process to get the second to last book in its proper place, and keep going until all books are sorted. This approach is called Bubble Sort. It's simple but slow. You'd make 1,279 comparisons in the first round, then 1,278, and so on, adding up to 818,560 comparisons. If each took just one second, the process would take over nine days. A second strategy would be to start by sorting just the first two books. Then, take the third book and compare it with the book in the second spot. If it belongs before the second book, swap them, then compare it with the book in the first spot, and swap again if needed. Now you've sorted the first three books. Keep adding one book at a time to the sorted sub-line, comparing and swapping the new book with the one before it until it's correctly placed among the books sorted so far. This is called Insertion Sort. Unlike Bubble Sort, it usually doesn't require comparing every pair of books. On average, we'd expect to only need to compare each book to half of the books that came before it. In that case, the total number of comparisons would be 409,280, taking almost five days. You're still doing way too many comparisons. Here's a better idea. First, pick a random book. Call it the partition and compare it to every other book. Then, divide the line by placing all the books that come before the partition on its left and all the ones that come after it on its right. You've just saved loads of time by not having to compare any of the books on the left to any of the ones on the right ever again. Now, looking only at the books on the left, you can again pick a random partition book and separate those books that come before it from those that come after it. You can keep creating sub-partitions like this until you have a bunch of small sub-lines, each of which you'd sort quickly using another strategy, like Insertion Sort. Each round of partitioning requires about 1,280 comparisons. If your partitions are pretty balanced, dividing the books into 128 sub-lines of ten would take about seven rounds, or 8,960 seconds. Sorting these sub-lines would add about 22 seconds each. All in all, this method known as QuickSort could sort the books in under three and a half hours. But there's a catch. Your partitions could end up lopsided, saving no time at all. Luckily, this rarely happens. That's why QuickSort is one of the most efficient strategies used by programmers today. They use it for things like sorting items in an online store by price, or creating a list of all the gas stations close to a given location sorted by distance. In your case, you're done quick sorting with time to spare. Just another high-stakes day in the library.

## Frequently Occurring Word Combinations

### ngrams of length 2

collocation frequency
insertion sort 2

## Important Words

3. afternoon
4. approach
5. arrives
6. automatic
7. average
8. balanced
9. beginning
10. belongs
11. book
12. books
13. broken
14. bubble
15. bunch
16. call
17. called
18. case
19. catch
20. classes
21. close
22. college
23. compare
24. comparing
25. comparisons
26. continue
27. correctly
28. creating
29. day
30. days
31. distance
32. divide
33. dividing
34. dropped
35. droves
36. efficient
37. expect
38. gas
39. hours
40. idea
41. insertion
42. items
43. leave
44. left
45. library
46. line
47. list
49. location
50. long
51. lopsided
52. luckily
53. matters
54. means
55. method
56. middle
57. morning
58. moving
59. needed
60. number
61. online
62. order
63. pair
64. partition
65. partitioning
66. partitions
67. pick
68. place
69. placing
70. point
71. pretty
72. price
73. process
74. programmers
75. proper
76. quick
77. quickly
78. quicksort
79. quiet
80. random
81. rarely
82. reach
83. reaches
84. repeat
85. require
86. requires
87. rounds
88. saved
89. saving
90. seconds
91. separate
92. shipment
93. show
94. simple
95. slow
96. small
97. sort
98. sorted
99. sorting
100. spare
101. spot
102. start
103. stations
104. store
105. straight
106. strategies
107. strategy
108. students
109. subsequent
110. suddenly
111. swap
112. swapping
113. system
114. ten
115. time
116. today
117. tomorrow
118. total
119. work
120. worse