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

วิธีใดที่จะจัดเรียงหนังสือตามตัวอักษรได้เร็วที่สุด - แชนด์ จอห์น (Chand John)

Translator: Trinsit Wasinudomrod Reviewer: Kelwalin Dhanasarnsombut

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 วินาที กระบวนการนี้จะใช้เวลาถึงเก้าวัน

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,

จะเป็น 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.

แต่ละรอบของการแบ่งกั้น ต้องใช้การเทียบ 1,280 ครั้ง

If your partitions are pretty balanced,

ถ้าพื้นที่แบ่งกั้นของคุณค่อนข้างสมดุล

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

การแบ่งหนังสือเป็นแถว 128 แถว แถวละสิบเล่ม จะต้องดำเนินการเจ็ดรอบ

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.

สามารถเรียงลำดับหนังสือ ได้ภายในสามชั่วโมงครึ่ง

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.

เป็นอีกหนึ่งวันหนึ่งที่เดิมพันสูง ณ ห้องสมุด