알파벳 순으로 책장을 정렬하는 가장 빠른 방법은 무엇일까?|챈드 죤(Chand John)

전체 강의 보기: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

당신은 대학 도서관에서 일하고 있습니다. 한가한 오후, 갑자기 1280권의 다양한 책들이 배송되었습니다. 책들은 한 줄로 놓여 졌지만 정렬되진 않았고, 자동분류 시스템도 망가졌습니다. 당신은 어떻게 이 책들을 빠르게 정렬할까요? 챈드 존이 어떻게 알고리즘이 도서관 사서들과 검색엔진이 빠르게 정보를 정렬할 수 있도록 돕는지 보여줍니다.

강의: 챈드 죤
애니메이션: 안톤 트로피모프

당신은 대학 도서관에서 일합니다.

조용한 오후,

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

책들은 한줄로 길게 놓아졌지만

정돈되어 있지는 않았고

자동 분류 시스템은 망가졌습니다.

더 심각한 문제는
내일 수업이 곧 시작되는데

이는 곧 내일 아침이 되자 마자

학생들이 떼지어 와서
책들을 찾느다는 겁니다.

어떻게 당신은 제 모든 책들을
제 시간 안에 정리할 수 있을까요?

한 방법은 한쪽 끝에 있는
책부터 시작하는 겁니다.

만약 첫 두 책이 순서대로 있다면,
그대로 두면 됩니다.

그게 아니라면 바꾸면 됩니다.

그리고는 두 번째와 세 번째의 책을 보고

그 과정을 반복하면 됩니다.

그리고 그렇게 마지막
책까지 계속하는 거죠.

어느 시점에서, 당신은 가장 마지막으로
가야 할 책을 만나게 될 것이고,

그 책을 매번 다른 책들과 순서를 바꿔

그 책이 제자리에 도착할 때까지
계속해서 뒤로 옮길 겁니다.

그리고 다시 맨 처음으로 가
이를 반복하면서

뒤에서 두 번째로 올
책을 제자리로 옮기고

모든 책들이 정리될 때까지 계속합니다.

이러한 방식을 거품정렬이라고 합니다.

간단하지만 느린 방법이죠.

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

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

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

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

두 번째 전략은 처음 두 책을
정리하는 것으로 시작합니다.

그리고 세 번째 책을 가져와
두 번째 자리에 있는 책과 비교합니다.

만약 이것이 두 번째 책 앞으로
가야한다면 바꾸고

첫 번째 자리에 있는 책과도 비교한 뒤

더 앞으로 가야한다면
또 위치를 바꿉니다.

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

계속해서 앞서 정돈 된 책들에 맞춰
다음 책을 한 권 씩 추가하고

새책을 그것 전의 책 한권과
비교하고 바꾸며

지금까지 정돈 된 책들 사이에서
알맞은 위치에 자리 할 때까지 반복합니다.

이것은 삽입정렬 이라고 합니다.

거품정렬과는 달리, 이는
모든 책을 일일이 비교할 필요가 없습니다.

평균적으로 , 우리는 각 책에 있어서
이미 정돈해 둔 책의

절반만을 비교하면
된다고 예측할 수 있습니다.

이 경우, 전체 비교 횟수는

409,280번이 되고,

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

당신은 아직도 너무
많은 비교를 하고 있습니다.

여기 더 좋은 생각이 있습니다.

먼저, 책 한 권을 무작위로 뽑으세요.

그것을 기준이라 부르고 이것을
다른 모든 책들과 비교해 보세요.

그리고 둘로 나누어서

기준보다 앞에 오는 책들은
왼쪽에 정돈하고

기준보다 뒤에 와야 하는 책들은
오른쪽에 정돈해봅시다.

당신은 방금 엄청난
시간을 절약했습니다.

왜냐하면 왼쪽에 있는 어떤 책들과

오른쪽에 있는 책들을
비교할 필요가 없기 때문이죠.

이제, 왼쪽에 있는 책들만 보면

당신은 다시 무작위로
기준이 되는 책을 고르고

책들을 기준 책 전과 후에
오는 것으로 나눌 수 있습니다.

이런 방식을 이용해
계속해서 기준 책을 만들고

수 많은 기준 책들이 생겼을 때

다른 전략, 삽입정렬을 이용해
빠르게 정렬할 수 있습니다.

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

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

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

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

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

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

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

하지만 여기엔 함정이 있습니다.

기준 책이 한쪽으로 쏠릴 수 있고,
이는 전혀 시간절약이 안 됩니다.

운이 좋은 것은, 이 경우는
매우 드물게 일어납니다.

이러한 이유로 퀵정렬은
프로그래머들이 이용하는

가장 효율적인 전략 중 하나죠.

프로그래머들은 온라인 쇼핑몰에서
물건들을 가격에 맞춰 정렬하거나

주어진 장소 주변의
모든 주유소들 거리에 따라

정렬하는 데 이용합니다.

당신의 경우에는, 퀵정렬로 끝내고
여유시간도 가질 수 있습니다.

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