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.
당신은 대학 도서관에서 일합니다. 조용한 오후, 갑자기 1,280권의 다양한 책들이 배송되었습니다. 책들은 한줄로 길게 놓아졌지만 정돈되어 있지는 않았고 자동 분류 시스템은 망가졌습니다. 더 심각한 문제는 내일 수업이 곧 시작되는데 이는 곧 내일 아침이 되자 마자 학생들이 떼지어 와서 책들을 찾느다는 겁니다. 어떻게 당신은 제 모든 책들을 제 시간 안에 정리할 수 있을까요? 한 방법은 한쪽 끝에 있는 책부터 시작하는 겁니다. 만약 첫 두 책이 순서대로 있다면, 그대로 두면 됩니다. 그게 아니라면 바꾸면 됩니다. 그리고는 두 번째와 세 번째의 책을 보고 그 과정을 반복하면 됩니다. 그리고 그렇게 마지막 책까지 계속하는 거죠. 어느 시점에서, 당신은 가장 마지막으로 가야 할 책을 만나게 될 것이고, 그 책을 매번 다른 책들과 순서를 바꿔 그 책이 제자리에 도착할 때까지 계속해서 뒤로 옮길 겁니다. 그리고 다시 맨 처음으로 가 이를 반복하면서 뒤에서 두 번째로 올 책을 제자리로 옮기고 모든 책들이 정리될 때까지 계속합니다. 이러한 방식을 거품정렬이라고 합니다. 간단하지만 느린 방법이죠. 당신은 첫 번째 정렬에서 1,279번을 비교할 것이고 그다음에는 1,278번을, 그리고 그 후에도 이와 같이 결국에는 총 818,560번의 비교를 하게 됩니다. 만약 비교 한번이 1초가 걸렸다면, 이 과정은 9일이 넘게 걸릴 겁니다. 두 번째 전략은 처음 두 책을 정리하는 것으로 시작합니다. 그리고 세 번째 책을 가져와 두 번째 자리에 있는 책과 비교합니다. 만약 이것이 두 번째 책 앞으로 가야한다면 바꾸고 첫 번째 자리에 있는 책과도 비교한 뒤 더 앞으로 가야한다면 또 위치를 바꿉니다. 이제 당신은 처음 3권을 정렬했습니다. 계속해서 앞서 정돈 된 책들에 맞춰 다음 책을 한 권 씩 추가하고 새책을 그것 전의 책 한권과 비교하고 바꾸며 지금까지 정돈 된 책들 사이에서 알맞은 위치에 자리 할 때까지 반복합니다. 이것은 삽입정렬 이라고 합니다. 거품정렬과는 달리, 이는 모든 책을 일일이 비교할 필요가 없습니다. 평균적으로 , 우리는 각 책에 있어서 이미 정돈해 둔 책의 절반만을 비교하면 된다고 예측할 수 있습니다. 이 경우, 전체 비교 횟수는 409,280번이 되고, 이는 거의 5일이 걸립니다. 당신은 아직도 너무 많은 비교를 하고 있습니다. 여기 더 좋은 생각이 있습니다. 먼저, 책 한 권을 무작위로 뽑으세요. 그것을 기준이라 부르고 이것을 다른 모든 책들과 비교해 보세요. 그리고 둘로 나누어서 기준보다 앞에 오는 책들은 왼쪽에 정돈하고 기준보다 뒤에 와야 하는 책들은 오른쪽에 정돈해봅시다. 당신은 방금 엄청난 시간을 절약했습니다. 왜냐하면 왼쪽에 있는 어떤 책들과 오른쪽에 있는 책들을 비교할 필요가 없기 때문이죠. 이제, 왼쪽에 있는 책들만 보면 당신은 다시 무작위로 기준이 되는 책을 고르고 책들을 기준 책 전과 후에 오는 것으로 나눌 수 있습니다. 이런 방식을 이용해 계속해서 기준 책을 만들고 수 많은 기준 책들이 생겼을 때 다른 전략, 삽입정렬을 이용해 빠르게 정렬할 수 있습니다. 어림잡아 1,280번 정도 기준 책으로 나누게 됩니다. 만약 당신의 기준 책들이 균형을 잘 맞다면 책들을 10권 씩으로 총 128 구간을 만드는 데 약 7번이 걸리는데 이는 약 8,960초가 걸립니다. 구간 안의 책들을 정리하는 데는 아마 22초 쯤 걸릴 겁니다. 전체적으로 이 방법은 퀵정렬이라고 알려져 있으며 모든 책을 3시간 반 만에 정렬할 수 있습니다. 하지만 여기엔 함정이 있습니다. 기준 책이 한쪽으로 쏠릴 수 있고, 이는 전혀 시간절약이 안 됩니다. 운이 좋은 것은, 이 경우는 매우 드물게 일어납니다. 이러한 이유로 퀵정렬은 프로그래머들이 이용하는 가장 효율적인 전략 중 하나죠. 프로그래머들은 온라인 쇼핑몰에서 물건들을 가격에 맞춰 정렬하거나 주어진 장소 주변의 모든 주유소들 거리에 따라 정렬하는 데 이용합니다. 당신의 경우에는, 퀵정렬로 끝내고 여유시간도 가질 수 있습니다. 정신없는 도서관에서의 또 하루가 지나가네요.