What's the fastest way to alphabetize your bookshelf? - Chand John

번역: Evee Kim 검토: Jihyeon J. Kim

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.

갑자기 1,280권의 다양한 책들이 배송되었습니다.

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,

당신은 첫 번째 정렬에서 1,279번을 비교할 것이고

then 1,278, and so on,

그다음에는 1,278번을, 그리고 그 후에도 이와 같이

adding up to 818,560 comparisons.

결국에는 총 818,560번의 비교를 하게 됩니다.

If each took just one second, the process would take over nine days.

만약 비교 한번이 1초가 걸렸다면, 이 과정은 9일이 넘게 걸릴 겁니다.

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.

이제 당신은 처음 3권을 정렬했습니다.

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,

409,280번이 되고,

taking almost five days.

이는 거의 5일이 걸립니다.

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.

어림잡아 1,280번 정도 기준 책으로 나누게 됩니다.

If your partitions are pretty balanced,

만약 당신의 기준 책들이 균형을 잘 맞다면

dividing the books into 128 sub-lines of ten would take about seven rounds,

책들을 10권 씩으로 총 128 구간을 만드는 데 약 7번이 걸리는데

or 8,960 seconds.

이는 약 8,960초가 걸립니다.

Sorting these sub-lines would add about 22 seconds each.

구간 안의 책들을 정리하는 데는 아마 22초 쯤 걸릴 겁니다.

All in all, this method known as QuickSort

전체적으로 이 방법은 퀵정렬이라고 알려져 있으며

could sort the books in under three and a half hours.

모든 책을 3시간 반 만에 정렬할 수 있습니다.

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.

정신없는 도서관에서의 또 하루가 지나가네요.