full transcript

From the Ted Talk by Chand John: What's the fastest way to alphabetize your bookshelf?

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.

Solution

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

  1. add
  2. adding
  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
  48. loads
  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