คุณทำงานที่ห้องสมุดวิทยาลัย
ณ ช่วงบ่ายอันแสนสงบ
ทันใดนั้นเอง หนังสือต่าง ๆ
จำนวน 1,280 เล่ม ก็เดินทางมาถึง
หนังสือส่งมาถึงในลักษณะ
ที่ถูกวางเรียงเป็นแถวยาวเรียงหนึ่ง
แต่พวกมันอยู่ในลำดับที่ไม่ถูกต้องเลย
และระบบเรียงลำดับอัตโนมัติก็ใช้งานไม่ได้
ที่แย่ไปกว่านั้นก็คือ
มหาวิทยาลัยจะเปิดเรียนพรุ่งนี้
ซึ่งหมายความว่าสิ่งแรกในช่วงเช้าก็คือ
นักศึกษาจะแห่กันมามองหาหนังสือเหล่านี้
คุณสามารถเรียงลำดับพวกมันทั้งหมด
ให้ทันเวลาได้อย่างไร
วิธีหนึ่งคือเริ่มต้นจากด้านหนึ่งของแถว
ด้วยหนังสือคู่แรก
ถ้าหนังสือคู่แรกเรียงลำดับถูกแล้ว
ให้ปล่อยมันไว้อย่างนั้น
ถ้าไม่ได้เป็นเช่นนั้น ก็ให้สลับลำดับพวกมัน
จากนั้นดูหนังสือเล่มที่สองและสาม
ทำกระบวนการเช่นนั้นซ้ำ
และทำต่อไปจนกระทั่งคุณไปถึงสุดแถว
เมื่อถึงจุดหนึ่ง คุณจะพบหนังสือเล่มหนึ่ง
ที่ควรจะเป็นเล่มสุดท้าย
และสลับมันกับหนังสือทุกเล่ม
ที่ตามหลังมันไปเรื่อย ๆ
ขยับมันลงไปจนกระทั่งถึงสุดแถว
ซึ่งเป็นตำแหน่งที่มันควรอยู่
จากนั้น เริ่มต้นจากหัวแถว
และทำกระบวนการนั้นซ้ำ
เพื่อให้หนังสือเล่มรองสุดท้าย
อยู่ในตำแหน่งที่มันควรอยู่
และทำซ้ำต่อไปเรื่อย ๆ จนกระทั่ง
หนังสือทั้งหมดถูกเรียงลำดับ
วิธีการนี้เรียกว่าการเรียงลำดับบับเบิล
มันง่ายแต่ช้า
คุณต้องทำการเทียบ 1,279 ครั้งในรอบแรก
จากนั้นอีก 1,278 ครั้ง และทำต่อไปอีก
รวมทั้งหมด 818,560 ครั้ง
ถ้าในแต่ละครั้งใช้เวลาแค่ 1 วินาที
กระบวนการนี้จะใช้เวลาถึงเก้าวัน
แนวทางที่สองคือการเริ่ม
ด้วยการเรียงลำดับหนังสือเพียงสองเล่มแรก
จากนั้นหยิบหนังสือเล่มที่สามและ
เทียบกับหนังสือในตำแหน่งที่สอง
ถ้ามันควรอยู่ก่อนหนังสือเล่มที่สอง
ให้สลับพวกมัน
จากนั้นเทียบมันกับหนังสือในตำแหน่งแรก
และสลับมันอีกครั้ง ถ้าจำเป็น
ตอนนี้คุณจัดเรียงหนังสือสามเล่มแรก
เป็นที่เรียบร้อยแล้ว
ค่อย ๆ เพิ่มหนังสือครั้งละหนึ่งเล่ม
เข้าไปในแถวย่อยที่เรียงลำดับแล้ว
เทียบและสลับหนังสือใหม่
กับหนังสือที่อยู่ก่อนหน้านั้น
จนกระทั่งมันอยู่ในตำแหน่งที่ถูกต้อง
ท่ามกลางหนังสือที่เรียงลำดับแล้ว
วิธีนี้เรียกว่าการเรียงลำดับอินเซอร์ชัน
แตกต่างจากการเรียงลำดับบับเบิล
ตามปกติแล้วเราไม่ต้องเทียบหนังสือทุกคู่
โดยเฉลี่ยเราคาดหวังว่า
เราต้องเทียบหนังสือแต่ละเล่ม
กับหนังสืออีกครึ่งหนึ่งที่อยู่ก่อนหน้ามัน
ในกรณีนั้น จำนวนการเทียบทั้งหมด
จะเป็น 409,280 ครั้ง
ซึ่งใช้เวลาเกือบห้าวัน
คุณยังคงต้องทำการเทียบมากเกินไป
เอาล่ะ นี่จะเป็นวิธีที่ดีกว่า
ก่อนอื่น สุ่มเลือกหนังสือขึ้นมาหนึ่งเล่ม
เรียกมันว่าตัวแบ่งกั้นและ
เทียบมันกับหนังสืออื่นทุก ๆ เล่ม
จากนั้น แบ่งแถวหนังสือ
โดยวางหนังสือที่มาก่อนหน้าตัวแบ่งกั้น
ไว้ทางซ้ายของมัน
และหนังสือที่ตามหลังตัวแบ่งกั้น
ไว้ทางขวาของมัน
คุณประหยัดเวลาได้มากเลย
เพราะไม่ต้องเทียบ
หนังสือใดก็ตามที่อยู่ทางซ้าย
กับหนังสือใดก็ตามที่อยู่ทางขวาอีก
ตอนนี้ ให้ความสนใจแต่หนังสือ
ที่อยู่ทางซ้ายเท่านั้น
คุณสามารถสุ่มเลือกตัวแบ่งกั้นอีกหนึ่งเล่ม
และแบ่งหนังสือที่มาก่อนตัวแบ่งกั้น
ออกจากหนังสือที่ตามหลังตัวแบ่งกั้น
คุณสามารถสร้างพื้นที่แบ่งกั้นเช่นนี้ได้เรื่อย ๆ
จนกระทั่งได้แถวย่อยเล็ก ๆ
ซึ่งคุณจะเรียงลำดับพวกมันได้อย่างรวดเร็ว
ด้วยวิธีอื่น เช่น การเรียงลำดับอินเซอร์ชัน
แต่ละรอบของการแบ่งกั้น
ต้องใช้การเทียบ 1,280 ครั้ง
ถ้าพื้นที่แบ่งกั้นของคุณค่อนข้างสมดุล
การแบ่งหนังสือเป็นแถว 128 แถว แถวละสิบเล่ม
จะต้องดำเนินการเจ็ดรอบ
หรือ 8,960 วินาที
การเรียงลำดับแถวย่อยเหล่านี้
เพิ่มเวลาราว 22 วินาทีต่อแถว
วิธีนี้ที่เรียกว่าการเรียงลำดับควิก
สามารถเรียงลำดับหนังสือ
ได้ภายในสามชั่วโมงครึ่ง
แต่มันก็มีจุดที่ต้องระวัง
การแบ่งกั้นของคุณอาจจะไม่สมดุล
และอาจไม่ได้ช่วยประหยัดเวลาเลย
แต่โชคดีที่มันไม่เกิดบ่อยนัก
นี่คือเหตุผลที่การเรียงลำดับควิก
คือหนึ่งในวิธีการที่มีประสิทธิภาพที่สุด
ที่โปรแกรมเมอร์ใช้กันในปัจจุบัน
พวกเขาใช้มันเพื่อเรียงลำดับสินค้า
ในร้านค้าออนไลน์ตามราคา
หรือการสร้างรายการสถานีบริการน้ำมัน
ที่อยู่ใกล้ตำแหน่งหนึ่ง ๆ
โดยเรียงลำดับตามระยะทาง
ในกรณีของคุณ คุณเรียงลำดับควิกจนเสร็จ
และยังมีเวลาเหลือ
เป็นอีกหนึ่งวันหนึ่งที่เดิมพันสูง ณ ห้องสมุด