Return to Video

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

  • 0:07 - 0:09
    คุณทำงานที่ห้องสมุดวิทยาลัย
  • 0:09 - 0:11
    ณ ช่วงบ่ายอันแสนสงบ
  • 0:11 - 0:18
    ทันใดนั้นเอง หนังสือต่าง ๆ
    จำนวน 1,280 เล่ม ก็เดินทางมาถึง
  • 0:18 - 0:22
    หนังสือส่งมาถึงในลักษณะ
    ที่ถูกวางเรียงเป็นแถวยาวเรียงหนึ่ง
  • 0:22 - 0:23
    แต่พวกมันอยู่ในลำดับที่ไม่ถูกต้องเลย
  • 0:23 - 0:27
    และระบบเรียงลำดับอัตโนมัติก็ใช้งานไม่ได้
  • 0:27 - 0:30
    ที่แย่ไปกว่านั้นก็คือ
    มหาวิทยาลัยจะเปิดเรียนพรุ่งนี้
  • 0:30 - 0:32
    ซึ่งหมายความว่าสิ่งแรกในช่วงเช้าก็คือ
  • 0:32 - 0:37
    นักศึกษาจะแห่กันมามองหาหนังสือเหล่านี้
  • 0:37 - 0:39
    คุณสามารถเรียงลำดับพวกมันทั้งหมด
    ให้ทันเวลาได้อย่างไร
  • 0:39 - 0:45
    วิธีหนึ่งคือเริ่มต้นจากด้านหนึ่งของแถว
    ด้วยหนังสือคู่แรก
  • 0:45 - 0:49
    ถ้าหนังสือคู่แรกเรียงลำดับถูกแล้ว
    ให้ปล่อยมันไว้อย่างนั้น
  • 0:49 - 0:51
    ถ้าไม่ได้เป็นเช่นนั้น ก็ให้สลับลำดับพวกมัน
  • 0:51 - 0:53
    จากนั้นดูหนังสือเล่มที่สองและสาม
  • 0:53 - 0:55
    ทำกระบวนการเช่นนั้นซ้ำ
  • 0:55 - 0:58
    และทำต่อไปจนกระทั่งคุณไปถึงสุดแถว
  • 0:58 - 1:01
    เมื่อถึงจุดหนึ่ง คุณจะพบหนังสือเล่มหนึ่ง
    ที่ควรจะเป็นเล่มสุดท้าย
  • 1:01 - 1:05
    และสลับมันกับหนังสือทุกเล่ม
    ที่ตามหลังมันไปเรื่อย ๆ
  • 1:05 - 1:09
    ขยับมันลงไปจนกระทั่งถึงสุดแถว
    ซึ่งเป็นตำแหน่งที่มันควรอยู่
  • 1:09 - 1:12
    จากนั้น เริ่มต้นจากหัวแถว
    และทำกระบวนการนั้นซ้ำ
  • 1:12 - 1:16
    เพื่อให้หนังสือเล่มรองสุดท้าย
    อยู่ในตำแหน่งที่มันควรอยู่
  • 1:16 - 1:19
    และทำซ้ำต่อไปเรื่อย ๆ จนกระทั่ง
    หนังสือทั้งหมดถูกเรียงลำดับ
  • 1:19 - 1:22
    วิธีการนี้เรียกว่าการเรียงลำดับบับเบิล
  • 1:22 - 1:24
    มันง่ายแต่ช้า
  • 1:24 - 1:29
    คุณต้องทำการเทียบ 1,279 ครั้งในรอบแรก
  • 1:29 - 1:34
    จากนั้นอีก 1,278 ครั้ง และทำต่อไปอีก
  • 1:34 - 1:39
    รวมทั้งหมด 818,560 ครั้ง
  • 1:39 - 1:44
    ถ้าในแต่ละครั้งใช้เวลาแค่ 1 วินาที
    กระบวนการนี้จะใช้เวลาถึงเก้าวัน
  • 1:44 - 1:49
    แนวทางที่สองคือการเริ่ม
    ด้วยการเรียงลำดับหนังสือเพียงสองเล่มแรก
  • 1:49 - 1:54
    จากนั้นหยิบหนังสือเล่มที่สามและ
    เทียบกับหนังสือในตำแหน่งที่สอง
  • 1:54 - 1:57
    ถ้ามันควรอยู่ก่อนหนังสือเล่มที่สอง
    ให้สลับพวกมัน
  • 1:57 - 2:00
    จากนั้นเทียบมันกับหนังสือในตำแหน่งแรก
  • 2:00 - 2:02
    และสลับมันอีกครั้ง ถ้าจำเป็น
  • 2:02 - 2:04
    ตอนนี้คุณจัดเรียงหนังสือสามเล่มแรก
    เป็นที่เรียบร้อยแล้ว
  • 2:04 - 2:08
    ค่อย ๆ เพิ่มหนังสือครั้งละหนึ่งเล่ม
    เข้าไปในแถวย่อยที่เรียงลำดับแล้ว
  • 2:08 - 2:12
    เทียบและสลับหนังสือใหม่
    กับหนังสือที่อยู่ก่อนหน้านั้น
  • 2:12 - 2:16
    จนกระทั่งมันอยู่ในตำแหน่งที่ถูกต้อง
    ท่ามกลางหนังสือที่เรียงลำดับแล้ว
  • 2:16 - 2:18
    วิธีนี้เรียกว่าการเรียงลำดับอินเซอร์ชัน
  • 2:18 - 2:23
    แตกต่างจากการเรียงลำดับบับเบิล
    ตามปกติแล้วเราไม่ต้องเทียบหนังสือทุกคู่
  • 2:23 - 2:27
    โดยเฉลี่ยเราคาดหวังว่า
    เราต้องเทียบหนังสือแต่ละเล่ม
  • 2:27 - 2:29
    กับหนังสืออีกครึ่งหนึ่งที่อยู่ก่อนหน้ามัน
  • 2:29 - 2:32
    ในกรณีนั้น จำนวนการเทียบทั้งหมด
  • 2:32 - 2:36
    จะเป็น 409,280 ครั้ง
  • 2:36 - 2:38
    ซึ่งใช้เวลาเกือบห้าวัน
  • 2:38 - 2:41
    คุณยังคงต้องทำการเทียบมากเกินไป
  • 2:41 - 2:43
    เอาล่ะ นี่จะเป็นวิธีที่ดีกว่า
  • 2:43 - 2:45
    ก่อนอื่น สุ่มเลือกหนังสือขึ้นมาหนึ่งเล่ม
  • 2:45 - 2:50
    เรียกมันว่าตัวแบ่งกั้นและ
    เทียบมันกับหนังสืออื่นทุก ๆ เล่ม
  • 2:50 - 2:52
    จากนั้น แบ่งแถวหนังสือ
  • 2:52 - 2:56
    โดยวางหนังสือที่มาก่อนหน้าตัวแบ่งกั้น
    ไว้ทางซ้ายของมัน
  • 2:56 - 2:59
    และหนังสือที่ตามหลังตัวแบ่งกั้น
    ไว้ทางขวาของมัน
  • 2:59 - 3:00
    คุณประหยัดเวลาได้มากเลย
  • 3:00 - 3:04
    เพราะไม่ต้องเทียบ
    หนังสือใดก็ตามที่อยู่ทางซ้าย
  • 3:04 - 3:07
    กับหนังสือใดก็ตามที่อยู่ทางขวาอีก
  • 3:07 - 3:10
    ตอนนี้ ให้ความสนใจแต่หนังสือ
    ที่อยู่ทางซ้ายเท่านั้น
  • 3:10 - 3:13
    คุณสามารถสุ่มเลือกตัวแบ่งกั้นอีกหนึ่งเล่ม
  • 3:13 - 3:17
    และแบ่งหนังสือที่มาก่อนตัวแบ่งกั้น
    ออกจากหนังสือที่ตามหลังตัวแบ่งกั้น
  • 3:17 - 3:20
    คุณสามารถสร้างพื้นที่แบ่งกั้นเช่นนี้ได้เรื่อย ๆ
  • 3:20 - 3:22
    จนกระทั่งได้แถวย่อยเล็ก ๆ
  • 3:22 - 3:28
    ซึ่งคุณจะเรียงลำดับพวกมันได้อย่างรวดเร็ว
    ด้วยวิธีอื่น เช่น การเรียงลำดับอินเซอร์ชัน
  • 3:28 - 3:33
    แต่ละรอบของการแบ่งกั้น
    ต้องใช้การเทียบ 1,280 ครั้ง
  • 3:33 - 3:35
    ถ้าพื้นที่แบ่งกั้นของคุณค่อนข้างสมดุล
  • 3:35 - 3:41
    การแบ่งหนังสือเป็นแถว 128 แถว แถวละสิบเล่ม
    จะต้องดำเนินการเจ็ดรอบ
  • 3:41 - 3:44
    หรือ 8,960 วินาที
  • 3:44 - 3:49
    การเรียงลำดับแถวย่อยเหล่านี้
    เพิ่มเวลาราว 22 วินาทีต่อแถว
  • 3:49 - 3:52
    วิธีนี้ที่เรียกว่าการเรียงลำดับควิก
  • 3:52 - 3:55
    สามารถเรียงลำดับหนังสือ
    ได้ภายในสามชั่วโมงครึ่ง
  • 3:55 - 3:56
    แต่มันก็มีจุดที่ต้องระวัง
  • 3:56 - 4:00
    การแบ่งกั้นของคุณอาจจะไม่สมดุล
    และอาจไม่ได้ช่วยประหยัดเวลาเลย
  • 4:00 - 4:01
    แต่โชคดีที่มันไม่เกิดบ่อยนัก
  • 4:01 - 4:05
    นี่คือเหตุผลที่การเรียงลำดับควิก
    คือหนึ่งในวิธีการที่มีประสิทธิภาพที่สุด
  • 4:05 - 4:07
    ที่โปรแกรมเมอร์ใช้กันในปัจจุบัน
  • 4:07 - 4:11
    พวกเขาใช้มันเพื่อเรียงลำดับสินค้า
    ในร้านค้าออนไลน์ตามราคา
  • 4:11 - 4:15
    หรือการสร้างรายการสถานีบริการน้ำมัน
    ที่อยู่ใกล้ตำแหน่งหนึ่ง ๆ
  • 4:15 - 4:16
    โดยเรียงลำดับตามระยะทาง
  • 4:16 - 4:20
    ในกรณีของคุณ คุณเรียงลำดับควิกจนเสร็จ
    และยังมีเวลาเหลือ
  • 4:20 - 4:23
    เป็นอีกหนึ่งวันหนึ่งที่เดิมพันสูง ณ ห้องสมุด
Title:
วิธีใดที่จะจัดเรียงหนังสือตามตัวอักษรได้เร็วที่สุด - แชนด์ จอห์น (Chand John)
Speaker:
Chand John
Description:

ดูบทเรียนฉบับเต็ม: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

คุณทำงานที่ห้องสมุดวิทยาลัย ทันใดนั้นเอง ณ ช่วงบ่ายที่เงียบสงบของคุณ หนังสือ 1,280 เล่มก็ถูกส่งมาถึง หนังสือเรียงเป็นแถวเรียงหนึ่ง แต่พวกมันอยู่ในลำดับที่ไม่ถูกต้องเลย และระบบเรียงลำดับอัตโนมัติก็ใช้งานไม่ได้ คุณจะเรียงลำดับหนังสืออย่างรวดเร็วได้อย่างไร แชนด์ จอห์น ให้ความกระจ่างว่าอัลกอริธึมช่วยบรรณารักษ์และเสิร์ชเอ็นจิ้นเรียงลำดับข้อมูลอย่างรวดเร็วได้อย่างไร

บทเรียนโดย แชนด์ จอห์น (Chand John) แอนิเมชันโดย แอนตัน โทรฟิมอฟ (Anton Trofimov)
more » « less
Video Language:
English
Team:
closed TED
Project:
TED-Ed
Duration:
04:39

Thai subtitles

Revisions

Our website uses cookies for analysis purposes.