การเรียงลำดับ (sorting) เป็นตัวอย่างสำคัญของกระบวนการคำนวณ นอกจากจะมีการใช้งานมากมายแล้ว การเรียงลำดับยังช่วยอธิบายแนวคิดพื้นฐานบางประการของวิทยาการคอมพิวเตอร์ด้วย ก่อนอื่น อัลกอริทึมการเรียงลำดับที่ต่างกันมีความต้องการเวลาและหน่วยความจำต่างกัน ซึ่งช่วยแสดงผลกระทบของประสิทธิภาพเมื่อเลือกวิธีแก้ปัญหาเชิงคอมพิวเตอร์ ต่อมา การเรียงลำดับเป็นปัญหาที่เรารู้ขอบเขตขั้นต่ำของความซับซ้อนในเชิงเวลา กล่าวคือ เราทราบ lower bound ของจำนวนขั้นตอนที่อัลกอริทึมเรียงลำดับใดๆ ต้องใช้ ดังนั้นการเรียงลำดับจึงแสดงให้เห็นว่าหลักการพื้นฐานของวิทยาการคอมพิวเตอร์สามารถระบุข้อจำกัดด้านความเร็วของการคำนวณได้ การรู้ขีดจำกัดเหล่านี้เป็นประโยชน์เพราะช่วยให้เรากำหนดทิศทางการวิจัยได้อย่างมีประสิทธิภาพ สุดท้าย อัลกอริทึมการเรียงลำดับหลายชนิดเป็นตัวอย่างของวิธีการแบบ divide-and-conquer — อัลกอริทึมจะแบ่งข้อมูลนำเข้าเป็นส่วนย่อย ๆ ประมวลผลแบบเรียกซ้ำ แล้วประกอบผลย่อยกลับเป็นคำตอบของปัญหาเดิม หลักการนี้สวยงามเพราะความเป็นแบบเรียกซ้ำและความเกี่ยวข้องกับการพิสูจน์ด้วยเหนี่ยวนำเชิงคณิตศาสตร์ มันเป็นแนวทางที่มีประสิทธิภาพมากในการแก้ปัญหาและแสดงพลังของการแยกปัญหาออกเป็นส่วนย่อย ตามที่กล่าวไว้ใน chapter 5 หนึ่งในการประยุกต์ของการเรียงลำดับคือช่วยสนับสนุนและเร่งการค้นหา ตัวอย่างเช่น การหาค่าในอาร์เรย์หรือลิสต์ที่ไม่ได้เรียงต้องใช้เวลาเชิงเส้น แต่ถ้าอาร์เรย์เรียงอยู่แล้ว เราสามารถค้นหาได้ในเวลาเชิงลอการิทึมด้วยการค้นหาแบบทวิภาค (binary search) ดังนั้นการคำนวณ (เช่นการเรียงลำดับ) ที่ทำไว้ก่อนหน้านี้สามารถถูกเก็บไว้ (ในรูปของอาร์เรย์ที่เรียงแล้ว) เพื่อใช้เร่งการคำนวณอื่นๆ ในภายหลังได้ โดยทั่วไปแล้ว การคำนวณเป็นทรัพยากรที่สามารถเก็บรักษาและนำกลับมาใช้ใหม่ผ่านโครงสร้างข้อมูล ความสัมพันธ์ระหว่างโครงสร้างข้อมูลและอัลกอริทึมแสดงให้เห็นว่าทั้งสองมีความเกี่ยวพันอย่างใกล้ชิด

First Things First (สิ่งที่ต้องทำก่อน)

สำหรับงานประจำ Indiana Jones เป็นอาจารย์ในวิทยาลัย ซึ่งหมายความว่าเขาต้องเผชิญกับงานที่เกี่ยวข้องกับการให้คะแนนข้อสอบ ดังนั้นการเรียงลำดับจึงมีความเกี่ยวข้องสำหรับเขายิ่งไปกว่านั้นในฐานะนักโบราณคดีเขาต้องเก็บคอลเลกชันของวัตถุโบราณและจัดระเบียบบันทึกกับการสังเกตจากการสำรวจของเขา เช่นเดียวกับเอกสารในสำนักงาน ข้อมูลเหล่านี้จะได้รับประโยชน์อย่างมากเมื่อเรียงลำดับเพราะลำดับจะทำให้การค้นหาสิ่งใดสิ่งหนึ่งมีประสิทธิภาพขึ้น การผจญภัยของ Indiana Jones แสดงให้เห็นอีกการประยุกต์ของการเรียงลำดับ ซึ่งเกิดขึ้นเมื่อใดก็ตามที่เขาจัดลำดับขั้นตอนเพื่อทำภารกิจที่ซับซ้อน แผนงานก็คือการจัดลำดับของชุดการกระทำในลำดับที่ถูกต้อง

ภารกิจของ Indiana Jones ใน Raiders of the Lost Ark คือการค้นหาหีบที่บรรจุ Ten Commandments เชื่อกันว่าหีบนั้นถูกฝังอยู่ในห้องลับในเมืองโบราณ Tanis เพื่อหาหีบ Indiana Jones ต้องค้นพบห้องลับนี้ที่เรียกว่า Well of Souls ตำแหน่งของห้องนี้สามารถพบได้จากแบบจำลองของ Tanis ซึ่งตั้งอยู่ในห้องแผนที่ โดยการวางแผ่นทองพิเศษไว้ที่ตำแหน่งหนึ่งในห้องแผนที่ แสงอาทิตย์จะถูกโฟกัสไปยังตำแหน่งของ Well of Souls ในแบบจำลองของ Tanis ทำให้ตำแหน่งของ Well of Souls ถูกเปิดเผย แผ่นทองดังกล่าวเดิมเป็นของอาจารย์และที่ปรึกษาของ Indiana Jones คือ Professor Ravenwood แต่ต่อมาก็ถูกให้แก่ลูกสาวของเขา Marion Ravenwood ดังนั้นเพื่อค้นหาหีบ Indiana Jones ต้องทำหลายงาน รวมถึงต่อไปนี้:

• ค้นหา Well of Souls (Well)
• หาห้องแผนที่ (Map)
• ได้รับแผ่นทอง (Disc)
• ใช้แผ่นทองเพื่อโฟกัสลำแสงอาทิตย์ (Sunbeam)
• ค้นหาผู้ที่ครอบครองแผ่นทอง (Marion)

นอกจากการทำงานที่กล่าวมาแล้ว Indiana Jones ยังต้องเดินทางระหว่างสถานที่ต่าง ๆ: ไปยังเนปาลเพื่อหาตัว Marion Ravenwood และไปยังเมือง Tanis ในอียิปต์ ซึ่งหีบถูกซ่อนอยู่ใน Well of Souls

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

Figure 6.1 Selection sort ทำการค้นหาองค์ประกอบที่เล็กที่สุดในรายการที่ยังไม่ได้เรียง (ด้านซ้ายของเส้นตั้ง) แล้วต่อเข้ากับรายการที่เรียงแล้ว (ด้านขวา) องค์ประกอบไม่ได้ถูกเรียงตามชื่อ แต่เรียงตามความขึ้นต่อกันของงานที่พวกมันแทน

วิธีแรก ตามที่แสดงใน figure 6.1 คือการค้นหาองค์ประกอบที่เล็กที่สุดในรายการที่ยังไม่ได้เรียงซ้ำ ๆ แล้วต่อเข้ากับรายการที่เรียงแล้ว เพื่อเปรียบเทียบการกระทำ หนึ่งการกระทำจะถือว่า "เล็กกว่า" การกระทำอีกอย่างหนึ่งถ้ามันสามารถเกิดขึ้นก่อนได้ ดังนั้นการกระทำที่เล็กที่สุดคือการกระทำที่ไม่จำเป็นต้องมีการกระทำอื่นมาก่อน ในตอนเริ่มต้นองค์ประกอบทั้งหมดยังต้องถูกประมวลผลและรายการที่เรียงแล้วยังว่างเปล่า เนื่องจากงานแรกคือการเดินทางไปยังเนปาล จึงถือว่า Nepal เป็นองค์ประกอบที่เล็กที่สุดและจึงเป็นองค์ประกอบแรกที่ถูกเลือกและต่อเข้ากับรายการที่เรียงแล้ว ขั้นตอนต่อไปคือการค้นหาผู้ที่ครอบครองแผ่นทอง นั่นคือ Marion จากนั้น Indiana Jones ต้องได้แผ่นทอง เดินทางไป Tanis และค้นพบห้องแผนที่ ซึ่งสะท้อนในบรรทัดที่สองถึงสุดท้ายใน figure 6.1 สุดท้าย Indiana Jones ต้องใช้แผ่นทองเพื่อโฟกัสลำแสงอาทิตย์เพื่อเปิดเผยตำแหน่งของ Well of Souls ซึ่งเขาจะพบหีบ รายการที่ได้คือแผนการผจญภัยของ Indiana Jones

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

Figure 6.2 Insertion sort ทำการแทรกองค์ประกอบถัดไปจากรายการที่ยังไม่ได้เรียง (ด้านซ้ายของเส้นตั้ง) เข้าไปในรายการที่เรียงแล้ว (ด้านขวา) ซ้ำ ๆ

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

ความพยายามส่วนใหญ่ใน selection sort ถูกใช้ไปกับการหาค่าเล็กที่สุดในรายการที่ยังไม่ได้เรียง แม้ว่ารายการที่ยังไม่ได้เรียงจะลดลงทีละองค์ประกอบ แต่เวลาทั้งหมดของอัลกอริทึมยังคงเป็นกำลังสอง เพราะเราต้องเดินรายการโดยเฉลี่ยแล้วเจอรายการที่มีครึ่งหนึ่งขององค์ประกอบทั้งหมด เราเห็นรูปแบบเดียวกันเมื่อวิเคราะห์อัลกอริทึมของ Hansel ใน chapter 2 สำหรับการหยิบก้อนกรวดถัดไปจากบ้าน: ผลรวมของตัวเลขแรก n เป็นปริมาณเชิงสัดส่วนต่อกำลังสองของ n.

วิธีที่นิยมอีกวิธีหนึ่งคือการหยิบองค์ประกอบใด ๆ (มักเป็นองค์ประกอบแรก) จากรายการที่ยังไม่ได้เรียงและวางมันที่ตำแหน่งที่ถูกต้องในรายการที่เรียงแล้ว องค์ประกอบจะถูกแทรกหลังองค์ประกอบที่ใหญ่ที่สุดในรายการที่เรียงแล้วซึ่งยัง "เล็กกว่า" องค์ประกอบที่จะถูกแทรก กล่าวอีกนัยหนึ่ง ขั้นตอนการแทรกจะเดินรายการที่เรียงแล้วเพื่อค้นหาองค์ประกอบตัวสุดท้ายที่ต้องมาก่อนองค์ประกอบที่จะถูกแทรก

ความพยายามของวิธีนี้ไปที่การแทรกองค์ประกอบ ไม่ใช่การเลือก ซึ่งเป็นที่มาของชื่อ insertion sort (ดู figure 6.2) Insertion sort เป็นวิธีที่ผู้เล่นไพ่จำนวนมากนิยมใช้ เมื่อมีไพ่กองหนึ่ง ผู้เล่นจะหยิบไพ่ทีละใบแล้วแทรกเข้าไปในมือที่เรียงแล้ว

ความต่างระหว่าง insertion sort และ selection sort ชัดเจนเมื่อย้ายองค์ประกอบ Sunbeam จากรายการที่ยังไม่ได้เรียงเข้าไปในรายการที่เรียงแล้ว ตามที่ figure 6.2 แสดง องค์ประกอบจะถูกนำออกจากรายการที่ยังไม่ได้เรียงโดยตรงโดยไม่ต้องค้นหา แล้วถูกแทรกเข้าในรายการที่เรียงแล้วโดยการเดินรายการจนกว่าจะพบตำแหน่งที่เหมาะสมระหว่าง Map และ Well

ตัวอย่างนี้ยังแสดงความแตกต่างเล็กน้อยในเวลารันของทั้งสองอัลกอริทึม ขณะที่ selection sort ต้องเดินหนึ่งในสองรายการให้สมบูรณ์สำหรับทุกองค์ประกอบที่เลือก insertion sort ทำเช่นนี้เฉพาะเมื่อองค์ประกอบที่จะแทรกมีค่ามากกว่าองค์ประกอบทั้งหมดในรายการที่เรียงแล้ว ในกรณีที่เลวร้ายที่สุด เมื่อรายการที่ต้องเรียงถูกจัดเรียงไว้แล้ว แต่ละองค์ประกอบจะถูกแทรกที่ท้ายของรายการที่เรียงแล้ว ในกรณีนี้ insertion sort มีเวลารันเท่ากับ selection sort ตรงกันข้าม เมื่อรายการเรียงจากมากไปน้อย (จากใหญ่ไปเล็ก) แต่ละองค์ประกอบจะถูกแทรกที่จุดหน้าของรายการที่เรียงแล้ว ซึ่งทำให้ insertion sort ทำงานในเวลาเชิงเส้น เราสามารถแสดงได้ว่าโดยเฉลี่ย insertion sort ยังคงมีเวลารันเป็นกำลังสอง แต่ในบางกรณี insertion sort อาจเร็วกว่ามากกว่าการเลือก และไม่เคยแย่กว่า

ทำไม insertion sort จึงมีเวลารันดีกว่า selection sort ในบางกรณี แม้ว่าทั้งสองจะทำงานคล้ายกัน? ความแตกต่างสำคัญคือ insertion sort ใช้ผลลัพธ์ของการคำนวณของมันเอง เนื่องจากองค์ประกอบใหม่ถูกแทรกเข้าไปในรายการที่เรียงแล้ว การแทรกจึงไม่จำเป็นต้องเดินรายการทั้งหมดเสมอ ในทางตรงกันข้าม selection sort จะต่อเข้ากับรายการที่เรียงแล้วเสมอ และเพราะกระบวนการเลือกไม่สามารถใช้ประโยชน์จากการเรียงได้ มันจึงต้องสแกนรายการที่ยังไม่ได้เรียงทั้งหมดเสมอ การเปรียบเทียบนี้แสดงหลักการออกแบบสำคัญของวิทยาการคอมพิวเตอร์คือการ reuse (การนำผลลัพธ์ที่มีอยู่มาใช้ซ้ำ)

นอกเหนือจากประสิทธิภาพแล้ว วิธีการทั้งสองเหมาะสมกับปัญหาการจัดลำดับการกระทำเพื่อทำแผนแค่ไหน? ไม่มีวิธีใดสมบูรณ์แบบ เพราะความยากพิเศษในตัวอย่างนี้ไม่ใช่กระบวนการเรียง แต่เป็นการตัดสินใจว่าองค์ประกอบใดต้องมาก่อนองค์ประกอบอื่น หากมีความไม่แน่นอนเกี่ยวกับการจัดลำดับที่แน่นอน selection sort ดูจะไม่น่าสนใจนัก เพราะในขั้นตอนแรกคุณต้องตัดสินใจแล้วว่าองค์ประกอบที่คิดว่าเป็น "เล็กสุด" จะเปรียบเทียบบกับองค์ประกอบอื่น ๆ อย่างไร Insertion sort ดีกว่าเพราะคุณสามารถหยิบองค์ประกอบใด ๆ มาเป็นขั้นตอนแรกโดยไม่ต้องเปรียบเทียบและได้รายการที่เรียงแล้วหนึ่งองค์ประกอบ แต่ในขั้นตอนถัดไป องค์ประกอบที่เลือกแต่ละตัวต้องถูกเปรียบเทียบกับองค์ประกอบจำนวนมากขึ้นในรายการที่เรียงแล้วเพื่อหาตำแหน่งที่ถูกต้อง ในตอนเริ่มต้นจำนวนการเปรียบเทียบที่ยากอาจน้อยกว่าใน insertion sort เมื่อเทียบกับ selection sort แต่บางครั้งอัลกอริทึมอาจบังคับการตัดสินใจที่เราอาจยังไม่สามารถทำได้ มีวิธีใดบ้างที่ให้ผู้เรียงควบคุมได้มากขึ้นว่าควรเปรียบเทียบองค์ประกอบใด?

Split as You Please (แบ่งตามสะดวก)

โดยทั่วไป วิธีการเรียงที่ดีควรอนุญาตให้เลื่อนการตัดสินใจที่ยากไว้ก่อนและเริ่มจากสิ่งที่ง่ายได้ ในกรณีแผนของ Indiana Jones เพื่อหาหีบ ตัวอย่างเช่นชัดเจนว่า Well of Souls และห้องแผนที่อยู่ใน Tanis ดังนั้นการกระทำที่เกี่ยวข้องกับสองสถานที่นั้นต้องมาหลังขั้นตอนการเดินทางไป Tanis และทุกสิ่งอื่นต้องมาก่อน

โดยการแบ่งองค์ประกอบของรายการออกเป็นกลุ่มที่มาก่อนและมาหลังองค์ประกอบที่แยกออก—เรียกว่า _pivot_—เราจะได้แยกรายการที่ยังไม่ได้เรียงออกเป็นสองรายการที่ยังไม่ได้เรียง แล้วเราได้ประโยชน์อะไรจากการทำเช่นนี้? แม้ว่าในตอนนั้นยังไม่มีอะไรถูกเรียง แต่เราบรรลุสองเป้าหมายสำคัญ ประการแรก เราได้ลดปัญหาการเรียงรายการยาวชุดหนึ่งให้เหลือการเรียงรายการสั้นลงสองชุด การทำให้ปัญหาเรียบง่ายขึ้นมักเป็นก้าวสำคัญสู่การแก้ปัญหา ประการที่สอง เมื่อสองปัญหาย่อยได้รับการแก้แล้ว—คือเมื่อสองรายการที่ยังไม่ได้เรียงถูกเรียงแล้ว—เราสามารถต่อผลลัพธ์เข้าด้วยกันเพื่อให้ได้รายการเรียงเดียวได้เลย กล่าวคือ การแยกปัญหาออกเป็นปัญหาย่อยช่วยให้ง่ายต่อการสร้างคำตอบของปัญหาหลักจากคำตอบของปัญหาย่อย

นี่เป็นผลมาจากวิธีการที่สองรายการย่อยถูกสร้างขึ้น สมมติให้ S เป็นรายการขององค์ประกอบที่ "เล็กกว่า" Tanis และ L เป็นรายการขององค์ประกอบที่ "ใหญ่กว่า" Tanis เราจึงรู้ว่าองค์ประกอบทั้งหมดใน S เล็กกว่าองค์ประกอบทั้งหมดใน L (แม้ว่า S และ L ยังไม่ได้เรียง) เมื่อต่อรายการ S กับ Tanis และ L เข้าด้วยกัน ผลลัพธ์จะเรียงแล้ว ดังนั้นขั้นตอนสุดท้ายคือการเรียงรายการ S และ L เมื่อทำเสร็จแล้วเราสามารถต่อผลลัพธ์เข้าด้วยกันได้เลย วิธีการเรียงรายการย่อยเหล่านี้คืออะไร? เราสามารถเลือกใช้วิธีใดก็ได้ เราอาจใช้วิธีการแยกและรวมแบบเรียกซ้ำ หรือถ้ารายการเล็กพอ เราอาจใช้วิธีง่าย ๆ เช่น selection sort หรือ insertion sort

ในปี 1960 นักวิทยาการคอมพิวเตอร์ชาวอังกฤษ Tony Hoare (ชื่อทางการ Sir Charles Antony Richard Hoare) คิดค้นวิธีการเรียงนี้ที่เรียกว่า quicksort Figure 6.3 แสดงการทำงานของ quicksort ในการสร้างแผนของ Indiana Jones ในขั้นตอนแรก รายการที่ยังไม่ได้เรียงจะถูกแบ่งออกเป็นสองรายการ โดยมีองค์ประกอบตัวคั่นคือ Tanis ในขั้นตอนต่อไป รายการย่อยทั้งสองจะต้องถูกเรียง เนื่องจากแต่ละรายการมีเพียงสามองค์ประกอบ เท่านี้ก็สามารถเรียงได้ง่ายด้วยอัลกอริทึมใด ๆ

สำหรับตัวอย่าง เรามาเรียงรายการย่อยขององค์ประกอบที่เล็กกว่า Tanis ด้วย quicksort หากเราเลือก Nepal เป็นองค์ประกอบตัวคั่น เราจะได้รายการที่ใหญ่กว่า Nepal คือ Disc → Marion ในขณะที่รายการขององค์ประกอบที่เล็กกว่า Tanis จะว่างเปล่า ซึ่งเรียงได้โดยปริยาย เพื่อเรียงรายการสององค์ประกอบนี้ เราเพียงเปรียบเทียบสององค์ประกอบและสลับตำแหน่งกัน จนได้รายการเรียง Nepal → Marion → Disc การเรียงจะทำงานในลักษณะเดียวกันถ้าเราเลือกองค์ประกอบอื่นเป็น pivot หากเราเลือก Disc เราจะได้รายการว่างและรายการสององค์ประกอบที่ต้องเรียง และถ้าเราเลือก Marion เราจะได้สองรายการที่มีหนึ่งองค์ประกอบซึ่งเรียงแล้ว การเรียงรายการย่อยที่ใหญ่กว่า Tanis ก็เป็นแบบเดียวกัน

Figure 6.3 Quicksort แบกรายการออกเป็นสองรายการย่อย ประกอบด้วยองค์ประกอบที่เล็กกว่าและใหญ่กว่า ตามลำดับ ขององค์ประกอบ pivot ที่เลือก จากนั้นรายการย่อยทั้งสองจะถูกเรียง และผลลัพธ์จะถูกต่อเข้าด้วยกันกับองค์ประกอบ pivot เพื่อให้ได้รายการที่เรียงแล้ว

เมื่อรายการย่อยถูกเรียงแล้ว เราสามารถต่อเข้าด้วยกันโดยมี Tanis อยู่ตรงกลางและได้ผลลัพธ์สุดท้าย ตามที่ figure 6.3 แสดง quicksort จะเข้าใกล้ผลลัพธ์อย่างรวดเร็วอย่างน่าประหลาด แต่สิ่งนี้เป็นจริงเสมอหรือไม่? เวลารันทั่วไปของ quicksort เป็นเท่าไร? ดูเหมือนว่าเราโชคดีที่เลือก Tanis เป็น pivot ในขั้นแรก เพราะ Tanis แบกรายการเป็นสองส่วนที่มีขนาดใกล้เคียงกัน หากเราสามารถเลือก pivot ที่มีสมบัตินี้ได้เสมอ รายการย่อยจะถูกแบ่งครึ่งเสมอ ซึ่งหมายความว่าจำนวนระดับของการแบ่งจะเป็นสัดส่วนของลอการิทึมของความยาวของรายการต้นฉบับ นี่หมายความว่าอย่างไรสำหรับเวลารันรวมของ quicksort ในกรณีนี้และในกรณีทั่วไป?

การวนรอบแรกซึ่งแบ่งรายการหนึ่งออกเป็นสองรายการใช้เวลาเชิงเส้น เพราะเราต้องตรวจสอบทุกองค์ประกอบในรายการ ในการวนรอบถัดไปเราต้องแบ่งสองรายการย่อย ซึ่งโดยรวมก็ใช้เวลาเชิงเส้นอีกครั้งเพราะจำนวนองค์ประกอบทั้งหมดในทั้งสองรายการมีค่าเท่ากับจำนวนองค์ประกอบเดิมลบหนึ่ง ไม่ว่าสัดส่วนจะเป็นอย่างไร และรูปแบบนี้ดำเนินต่อไป: แต่ละระดับไม่มีองค์ประกอบมากกว่าระดับก่อนหน้า ดังนั้นแต่ละระดับจึงใช้เวลาเชิงเส้นในการแบ่ง รวมทั้งหมดเราจะสะสมเวลาเชิงเส้นสำหรับแต่ละระดับ ซึ่งหมายความว่าเวลารันของ quicksort ขึ้นอยู่กับจำนวนระดับที่ต้องการในการแบ่งรายการย่อย เมื่อรายการต้นฉบับถูกแยกจนเหลือองค์ประกอบเดี่ยว กระบวนการแบ่งจะทำให้องค์ประกอบเหล่านี้อยู่ในลำดับที่ถูกต้องและสามารถเชื่อมต่อกันเป็นรายการเรียงแล้วได้ ซึ่งขั้นตอนนี้ก็ต้องใช้เวลาเชิงเส้นอีกครั้ง ดังนั้นเวลารวมของ quicksort ถูกกำหนดโดยผลรวมของเวลาเชิงเส้นสำหรับแต่ละระดับ

Figure 6.4 การเปรียบเทียบเวลารันในรูปแบบ linearithmic, linear และ quadratic

ในกรณีที่ดีที่สุด เมื่อเราสามารถแบ่งแต่ละรายการย่อยได้ประมาณครึ่ง ๆ เราจะได้จำนวนระดับเป็นสัดส่วนของลอการิทึม ยกตัวอย่าง รายการ 100 องค์ประกอบนำไปสู่ 7 ระดับ รายการ 1,000 องค์ประกอบนำไปสู่ 10 ระดับ และรายการ 1,000,000 องค์ประกอบสามารถแยกจนหมดได้เพียง 20 ระดับ สำหรับเวลารวม นั่นหมายความว่าในกรณีของ 1,000,000 องค์ประกอบ เราต้องเสียเวลาเชิงเส้นในการสแกนรายการขนาด 1,000,000 เพียง 20 ครั้ง ซึ่งนำไปสู่เวลารันที่มีจำนวนก้าวในระดับสิบล้าน ซึ่งดีกว่ามากเมื่อเทียบกับเวลารันกำลังสองซึ่งหมายถึงร้อยพันล้านถึงล้านล้านก้าว พฤติกรรมเวลารันนี้ ซึ่งเวลารันเพิ่มขึ้นตามขนาดของข้อมูลคูณด้วยลอการิทึมของขนาด เรียกว่า linearithmic มันไม่ดีเท่าเวลารันเชิงเส้น แต่ดีกว่ากำลังสองมาก (ดู figure 6.4)

ในกรณีดีที่สุด quicksort มีเวลารันแบบ linearithmic อย่างไรก็ตาม หากเราเลือก pivot ไม่ดี สถานการณ์จะแตกต่างอย่างมาก ตัวอย่างเช่น ถ้าเราเลือก Nepal แทน Tanis เป็น pivot แรก รายการย่อยที่เล็กกว่าจะว่างเปล่า และรายการย่อยที่ใหญ่กว่าจะประกอบด้วยองค์ประกอบทั้งหมดยกเว้น Nepal ถ้าเราต่อด้วยการเลือก Marion เป็น pivot ของรายการย่อยนั้น เราจะเจอสถานการณ์เดิมอีกครั้งที่หนึ่งในรายการว่างและอีกรายการสั้นลงเพียงองค์ประกอบเดียวจากรายการย่อยที่กำลังถูกแบ่ง ในกรณีนี้ quicksort จะทำงานเหมือน selection sort โดยที่มันจะค่อย ๆ เอาองค์ประกอบที่เล็กที่สุดออกจากรายการที่ยังไม่ได้เรียง ดังนั้น quicksort ก็จะมีเวลารันเป็นกำลังสองเช่นกัน ประสิทธิภาพของ quicksort ขึ้นกับการเลือก pivot: ถ้าเราสามารถหาผลึกกลางได้เสมอ กระบวนการแบ่งจะได้รายการย่อยที่แบ่งอย่างสมดุล แต่จะหาพ pivot ที่ดีได้อย่างไร? แม้จะไม่ง่ายที่จะการันตีการเลือก pivot ที่ดี แต่วิธีการสุ่มเลือกองค์ประกอบหรือใช้ median ขององค์ประกอบตัวแรก ตัวกลาง และตัวสุดท้ายมักให้ผลลัพธ์ที่ดีโดยเฉลี่ย

ความสำคัญและผลกระทบของ pivot เกี่ยวข้องอย่างใกล้ชิดกับแนวคิดของ boundary ที่ถูกใช้ใน chapter 5 เพื่ออธิบายแก่นของการค้นหา ที่นี่จุดประสงค์ของ boundary คือแบ่งพื้นที่ค้นหาให้ออกเป็นด้านนอกและด้านในเพื่อให้ด้านในเล็กที่สุดเท่าที่จะเป็นไปได้เพื่อให้งานค้นหาที่เหลือทำได้ง่ายขึ้น ในกรณีของการเรียง boundary ควรแบ่งพื้นที่การเรียงให้ออกเป็นส่วนที่เท่า ๆ กัน เพื่อให้การเรียงของแต่ละส่วนง่ายขึ้น ดังนั้นหาก pivot ถูกเลือกไม่ดี เวลารันของ quicksort จะเสื่อมลง แต่แม้ว่า quicksort จะมีเวลารันเป็นกำลังสองในกรณีที่เลวร้ายที่สุด มันก็มีเวลารันแบบ linearithmic โดยเฉลี่ย และทำงานได้ดีในทางปฏิบัติ

The Best Is Yet to Come (สิ่งที่ดีที่สุดยังรออยู่)

มีวิธีการเรียงที่เร็วกว่าควิกซอร์ตอีกไหม เช่น อัลกอริทึมที่มีเวลารันแบบ linearithmic หรือน้อยกว่าในกรณีที่เลวร้ายที่สุด? คำตอบคือมี หนึ่งในอัลกอริทึมเหล่านั้นคือ mergesort ซึ่งคิดค้นโดยนักคณิตศาสตร์ชาวฮังการี-อเมริกัน John von Neumann ในปี 1945 Mergesort แบกรายการที่ยังไม่ได้เรียงออกเป็นสองส่วน ทำงานโดยการแยกปัญหาเป็นส่วนย่อยเหมือนกับ quicksort อย่างไรก็ตาม mergesort ไม่เปรียบเทียบองค์ประกอบในขั้นตอนการแบ่ง มันแบ่งรายการเป็นสองส่วนที่มีขนาดเท่ากัน เมื่อรายการย่อยทั้งสองถูกเรียงแล้ว เราสามารถรวมพวกมันเป็นรายการเรียงเดียวได้โดยการเดินทั้งสองรายการพร้อมกันและเปรียบเทียบองค์ประกอบทีละตัว โดยทำการเปรียบเทียบองค์ประกอบแรกของทั้งสองรายการย่อยซ้ำ ๆ แล้วเลือกองค์ประกอบที่เล็กกว่า เนื่องจากทั้งสองรายการย่อยนั้นเรียงอยู่แล้ว การรวมแบบนี้จึงให้รายการที่เรียงแล้ว แต่แล้วเราจะเรียงทั้งสองรายการย่อยที่ได้จากการแบ่งได้อย่างไร? นั่นทำได้โดยการประยุกต์ใช้ mergesort แบบเรียกซ้ำกับทั้งสองรายการ Mergesort แสดงใน figure 6.5

ขณะที่ quicksort และ mergesort เป็นอัลกอริทึมที่ยอดเยี่ยมสำหรับการเขียนโปรแกรมบนคอมพิวเตอร์ไฟฟ้า แต่สำหรับความจำของมนุษย์ที่ไม่มีเครื่องช่วย พวกมันอาจจะไม่สะดวกนัก เพราะต้องมีการเก็บข้อมูลชั่วคราวค่อนข้างมาก โดยเฉพาะอย่างยิ่งสำหรับรายการขนาดใหญ่ อัลกอริทึมทั้งสองต้องรักษาคอลเลกชันของรายการย่อยจำนวนมาก ในกรณีของ quicksort รายการเหล่านี้ยังต้องอยู่ในลำดับที่ถูกต้อง ดังนั้น Indiana Jones เช่นเดียวกับเรา อาจยังคงใช้ insertion sort เวอร์ชันที่ถูกปรับแต่งเล็กน้อย เว้นแต่ขนาดของรายการที่จะเรียงจะบังคับให้ใช้วิธีที่มีประสิทธิภาพกว่า ตัวอย่างเช่น เมื่อฉันสอนชั้นเรียนระดับปริญญาตรีขนาดใหญ่ ฉันใช้รูปแบบของ bucket sort สำหรับการเรียงข้อสอบโดยชื่อนิสิต โดยจัดข้อสอบลงในกอง (เรียกว่า buckets) ตามตัวอักษรตัวแรกของนามสกุล และรักษาความเรียงในแต่ละบัคเก็ตด้วย insertion sort เมื่อจัดข้อสอบทุกใบลงในบัคเก็ตแล้ว ก็สามารถต่อบัคเก็ตตามลำดับตัวอักษรเพื่อให้ได้รายการที่เรียงแล้ว Bucket sort คล้ายกับ counting sort (ที่จะกล่าวถึงต่อไป)

Figure 6.5 Mergesort แบกรายการออกเป็นสองรายการย่อยที่มีขนาดเท่ากัน เรียงรายการย่อยเหล่านั้น แล้วรวมผลที่เรียงแล้วเข้าเป็นรายการเดียว วงเล็บระบุลำดับที่รายการย่อยต้องถูกรวม ในบรรทัดที่ 4 การแยกจะเสร็จเมื่อได้รายการที่มีเพียงองค์ประกอบเดียวเท่านั้น ในบรรทัดที่ 5 คู่ของรายการองค์ประกอบเดี่ยวทั้งสามคู่ถูกรวมกันเป็นสามรายการที่เรียงแล้วซึ่งมีสององค์ประกอบ และในบรรทัดที่ 6 รายการเหล่านั้นถูกรวมอีกครั้งเป็นรายการสี่องค์ประกอบหนึ่งรายการและรายการสามองค์ประกอบหนึ่งรายการ ซึ่งถูกรวมในขั้นตอนสุดท้ายเพื่อให้ได้ผลลัพธ์สุดท้าย

บนผิวเผิน mergesort ดูซับซ้อนกว่า quicksort แต่ส่วนหนึ่งอาจมาจากการที่บางขั้นตอนถูกข้ามในคำอธิบายของ quicksort อย่างไรก็ตามดูเหมือนว่าการรวมรายการที่ยาวขึ้นซ้ำ ๆ จะไม่มีประสิทธิภาพ แต่ง่ายจะหลงทาง ความคิดนี้ทำให้เข้าใจผิด เพราะการแยกเป็นระบบและการแบ่งรายการครึ่งหนึ่งในทุกขั้นตอน ทำให้ประสิทธิภาพโดยรวมดี: ในกรณีที่เลวร้ายที่สุด เวลาในการรันของ mergesort เป็นแบบ linearithmic ซึ่งสามารถเห็นได้ดังนี้ ประการแรก เนื่องจากเราจะแบกรายการครึ่งหนึ่งอยู่เสมอ จำนวนครั้งที่ต้องแยกรายการเป็นสัดส่วนของลอการิทึม ประการที่สอง การรวมในแต่ละระดับใช้เวลาเชิงเส้นเพราะเราต้องประมวลผลแต่ละองค์ประกอบเพียงครั้งเดียว (ดู figure 6.5) สุดท้าย การรวมเกิดขึ้นในแต่ละระดับเพียงครั้งเดียว เราจึงได้เวลาแบบ linearithmic ทั้งหมด

Mergesort มีความคล้ายคลึงกับ quicksort ในแง่ที่ว่าอัลกอริทึมทั้งสองมีเฟสของการแบ่งรายการ ตามด้วยขั้นตอนการเรียงแบบเรียกซ้ำสำหรับแต่ละรายการย่อย และสุดท้ายคือเฟสการรวมรายการย่อยที่เรียงแล้วให้เป็นรายการยาวขึ้น ที่จริงแล้วทั้ง quicksort และ mergesort เป็นตัวอย่างของอัลกอริทึมแบบ divide-and-conquer ซึ่งเป็นกรอบทั่วไปดังนี้:

ถ้าปัญหาเป็นเรื่องง่าย แก้โดยตรง

ถ้าไม่

(1) แยกปัญหาออกเป็นปัญหาย่อย

(2) แก้ปัญหาย่อยเหล่านั้น

(3) รวมคำตอบของปัญหาย่อยให้เป็นคำตอบของปัญหาใหญ่

ตัวอย่างของการแก้ปัญหาที่ไม่ง่ายแสดงให้เห็นการทำงานของ divide-and-conquer ขั้นตอนแรกคือขั้นตอน divide ซึ่งลดความซับซ้อนของปัญหา ขั้นตอนที่สองคือการประยุกต์วิธีแบบเรียกซ้ำกับปัญหาย่อย หากปัญหาย่อยที่ได้มีขนาดเล็กพอ ก็สามารถแก้ได้โดยตรง มิฉะนั้นจะถูกแยกย่อยต่อไปจนเล็กพอที่จะแก้ได้โดยตรง ขั้นตอนที่สามคือขั้นตอน merge ซึ่งเป็นการประกอบคำตอบของปัญหาย่อยให้เป็นคำตอบของปัญหาใหญ่

Quicksort ทำงานหนักที่สุดในขั้นตอน divide ซึ่งเป็นจุดที่เกิดการเปรียบเทียบองค์ประกอบทั้งหมด: โดยการรับรองว่าองค์ประกอบในสองรายการถูกแยกด้วย pivot จะทำให้ขั้นตอน merge เป็นการต่อรายการธรรมดา ในทางกลับกัน ขั้นตอน divide ของ mergesort ค่อนข้างเรียบง่ายและไม่มีการเปรียบเทียบองค์ประกอบ งานส่วนใหญ่ของ mergesort เกิดขึ้นในขั้นตอน merge ที่รวมรายการที่เรียงแล้วเข้าด้วยกัน คล้ายกับการรูดซิป

The Quest Is Over: No Better Sorting Algorithm, Ever (คำค้นพบ: ไม่มีอัลกอริทึมการเรียงที่ดีกว่านี้ตลอดไป)

Mergesort เป็นวิธีการเรียงที่มีประสิทธิภาพที่สุดที่กล่าวถึงจนถึงตอนนี้ แต่จะเรียงได้เร็วกว่านี้อีกไหม? คำตอบคือทั้งใช่และไม่ใช่ แม้ว่าโดยทั่วไปเราไม่สามารถเรียงได้เร็วกว่ากรณีทั่วไป แต่เราสามารถทำได้ดีกว่าเมื่อมีสมมติฐานพิเศษเกี่ยวกับค่าขององค์ประกอบที่จะเรียง ตัวอย่างเช่น ถ้าเราทราบว่ารายการที่จะเรียงมีเฉพาะตัวเลขในช่วง 1 ถึง 100 เราสามารถสร้างอาร์เรย์ที่มี 100 เซลล์ หนึ่งเซลล์สำหรับแต่ละจำนวนที่เป็นไปได้ วิธีการนี้คล้ายกับ bucket sort ที่มีหนึ่งกองสำหรับแต่ละตัวอักษร ในที่นี้แต่ละเซลล์ของอาร์เรย์สอดคล้องกับกองที่เก็บตัวเลขหนึ่งค่า เซลล์อาร์เรย์ถูกจัดหมายเลขตั้งแต่ 1 ถึง 100 เราใช้แต่ละเซลล์ที่มีดัชนี i เพื่อเก็บจำนวนครั้งที่ i ปรากฏในรายการ ก่อนอื่นเรากำหนดค่าเป็น 0 ในแต่ละเซลล์ของอาร์เรย์ เพราะเราไม่รู้ว่าตัวเลขใดอยู่ในรายการ จากนั้นเราเดินรายการ และสำหรับแต่ละองค์ประกอบ i ที่เจอ เราจะเพิ่มค่าตัวนับในเซลล์ที่มีดัชนี i สุดท้ายเราเดินอาร์เรย์ตามลำดับดัชนีที่เพิ่มขึ้นและใส่แต่ละดัชนีลงในรายการผลซ้ำตามจำนวนที่ตัวนับของเซลล์บอกไว้ ตัวอย่างเช่น ถ้ารายการที่จะเรียงคือ 4→2→5→4→2→6 เราจะได้อาร์เรย์ดังต่อไปนี้หลังจากเดินรายการ:

เมื่อตรวจอาร์เรย์เราจะพบว่า 1 ไม่ปรากฏในรายการเพราะตัวนับยังคงเป็น 0 ดังนั้น 1 จะไม่อยู่ในรายการผลที่เรียง ในทางตรงกันข้าม ค่า 2 ปรากฏสองครั้งและจะถูกใส่สองครั้งเข้าไปในรายการ ผลลัพธ์สุดท้ายจะเป็น 2→2→4→4→5→6 วิธีการนี้เรียกว่า counting sort เพราะอาร์เรย์เก็บตัวนับความถี่ขององค์ประกอบที่ปรากฏในการเรียง เวลารันของ counting sort มาจากค่าใช้จ่ายรวมของการเดินรายการและการเดินอาร์เรย์ เนื่องจากแต่ละขั้นตอนใช้เวลาเชิงเส้นตามขนาดของโครงสร้างข้อมูลที่เกี่ยวข้อง (รายการและอาร์เรย์) ดังนั้น counting sort จึงทำงานในเวลาเชิงเส้นเมื่อเทียบกับขนาดของรายการหรืออาร์เรย์แล้วแต่ค่าที่มากกว่า

ข้อเสียของ counting sort คือมันอาจเปลืองพื้นที่มาก ในตัวอย่าง เซลล์ที่มีดัชนีตั้งแต่ 7 ถึง 100 ไม่ถูกใช้เลย นอกจากนี้มันใช้ได้เฉพาะเมื่อองค์ประกอบสามารถใช้เป็นดัชนีของอาร์เรย์ได้และช่วงของค่าของรายการเป็นที่รู้และไม่กว้างเกินไป เช่น เราไม่สามารถเรียงรายการชื่อด้วย counting sort ได้เพราะชื่อนั้นเป็นลำดับของตัวอักษรและไม่สามารถใช้เป็นดัชนีของอาร์เรย์ได้ ยังมีอัลกอริทึมการเรียงเฉพาะสำหรับรายการของสตริง เช่น โครงสร้างข้อมูล trie (ดู chapter 5) สามารถใช้เรียงรายการสตริงได้ แต่วิธีเหล่านั้นมีสมมติฐานอื่น ๆ เกี่ยวกับองค์ประกอบที่จะเรียง

As Good as It Gets (ดีเท่าที่จะเป็นไปได้)

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

ความเป็น optimal ของ mergesort พึ่งพาสองข้อเท็จจริงที่เกี่ยวข้องกันแต่แตกต่างกัน Mergesort มีเวลารันแบบ linearithmic และอัลกอริทึมการเรียงใด ๆ สำหรับกรณีทั่วไปต้องมีเวลารันอย่างน้อยแบบ linearithmic ข้อที่สองนี้เป็นเหตุผลที่ยืนยันความเป็น optimal ของ mergesort และสำหรับอัลกอริทึมการเรียงอื่น ๆ ที่มีเวลารัน linearithmic ในกรณีที่เลวร้ายที่สุดด้วย เป้าหมายสูงสุดในการออกแบบอัลกอริทึมและโครงสร้างข้อมูลคือการหาวิธีแก้ปัญหาที่ optimal นั่นคืออัลกอริทึมที่เวลารันในกรณีที่เลวร้ายที่สุดตรงกับความซับซ้อนโดยเนื้อแท้ของปัญหาที่มันแก้ อัลกอริทึมดังกล่าวอาจถือได้ว่าเป็น Holy Grail ของปัญหานั้น และเช่นเดียวกับ Indiana Jones ใน The Last Crusade John von Neumann พบ Holy Grail ของการเรียงใน mergesort

การแยกความแตกต่างระหว่างเวลารันของอัลกอริทึมกับความซับซ้อนของปัญหาเป็นเรื่องสำคัญ ความหลังบอกว่าการแก้ปัญหาที่ถูกต้องต้องใช้ อย่างน้อย จำนวนก้าวดังกล่าว ในทางกลับกัน เวลารันของอัลกอริทึมบอกว่าอัลกอริทึมเฉพาะนั้นใช้ อย่างมากที่สุด กี่ก้าว คำกล่าวเกี่ยวกับความซับซ้อนขั้นต่ำของปัญหาถือเป็น lower bound ของปัญหา Lower bound ให้ประมาณการว่างานของปัญหาจะต้องใช้การทำงานขั้นต่ำเท่าใดและจึงกำหนดความซับซ้อนโดยเนื้อแท้ของปัญหา มันคล้ายกับระยะทางเชิงเรขาคณิตระหว่างสองจุด ซึ่งเป็น lower bound สำหรับเส้นทางใด ๆ ที่เชื่อมจุดทั้งสอง เส้นทางใด ๆ อาจยาวกว่าระยะทางจริงเพราะมีอุปสรรค แต่จะไม่สั้นกว่าระยะทาง ความรู้สึกผิดหวังที่อาจเกิดขึ้นต่อ lower bound ของการเรียงและข้อจำกัดของอัลกอริทึมควรถูกชดเชยด้วยความเข้าใจเชิงลึกที่ข้อมูลนี้ให้เกี่ยวกับปัญหาการเรียง เปรียบเทียบกับผลลัพธ์จากสาขาอื่น เช่น ในฟิสิกส์เรารู้ว่าไม่สามารถเดินทางเร็วกว่าแสงและเราไม่สามารถสร้างพลังงานจากความว่างเปล่า

แต่เราจะมั่นใจใน lower bound ของการเรียงได้อย่างไร? อาจมีอัลกอริทึมที่ยังไม่มีใครคิดค้นซึ่งทำงานได้เร็วกว่ากำลังสองเชิงลอการิทึม การพิสูจน์สิ่งที่เป็นลบไม่ง่ายเพราะต้องแสดงว่าอัลกอริทึมใด ๆ ที่มีอยู่หรือที่จะถูกประดิษฐ์ขึ้นต้องทำขั้นตอนขั้นต่ำบางอย่าง ข้อโต้แย้งสำหรับ lower bound ของการเรียงจะนับจำนวนรายการที่เป็นไปได้สำหรับความยาวเฉพาะ และแสดงว่าจำนวนการเปรียบเทียบที่จำเป็นในการระบุรายการที่เรียงแล้วเป็นแบบ linearithmic. เนื่องจากอัลกอริทึมทุกชนิดต้องทำการเปรียบเทียบขั้นต่ำนี้ จึงสรุปได้ว่าอัลกอริทึมใด ๆ ต้องการอย่างน้อยจำนวนขั้นตอนแบบ linearithmic ซึ่งพิสูจน์ lower bound

การให้เหตุผลเกี่ยวกับเวลารันของอัลกอริทึมและ lower bounds อาศัยสมมติฐานเรื่องความสามารถของคอมพิวเตอร์ที่รันอัลกอริทึม ตัวอย่างเช่น สมมติฐานทั่วไปคือขั้นตอนของอัลกอริทึมถูกดำเนินการตามลำดับและใช้เวลาหน่วยหนึ่งสำหรับแต่ละขั้นตอน สมมติฐานเหล่านี้ก็เป็นฐานของการวิเคราะห์อัลกอริทึมเรียงที่กล่าวถึงในบทนี้ อย่างไรก็ตามถ้าเราสมมติว่าเราสามารถทำการเปรียบเทียบพร้อมกันแบบขนานได้ การวิเคราะห์ก็จะเปลี่ยนไปและเราอาจได้ผลลัพธ์แตกต่างกันสำหรับเวลารันและ lower bounds

Computation Preservation (การอนุรักษ์การคำนวณ)

ดูเหมือนว่า Indiana Jones ค่อนข้างเป็นระเบียบในการเตรียมตัวออกผจญภัย: เขามักเก็บหมวกและแส้ไว้ในกระเป๋าเดินทาง แทนที่จะวางแผนทุกขั้นตอนอย่างละเอียด เขาอาจเลือกวิธีการตัดสินใจทีละขั้นตอนเมื่อถึงเวลา ทั้งสองแนวทาง—การวางแผนล่วงหน้าและการตัดสินใจตามสถานการณ์—มีข้อดีข้อเสียแตกต่างกัน การเดินทางไปขั้วโลกเหนือต้องการเสื้อผ้าและอุปกรณ์ต่างจากการไปอเมซอน ในกรณีนี้การวางแผนล่วงหน้าดูจะเป็นความคิดที่ดี แต่สภาพการณ์ที่เปลี่ยนแปลงอาจทำให้แผนก่อนหน้าล้าสมัยและทำให้ความพยายามในการวางแผนไร้ประโยชน์ โดยเฉพาะในระหว่างการผจญภัยสิ่งที่ไม่คาดคิดอาจเกิดขึ้นซึ่งมักต้องทำการกระทำต่างจากที่คาดไว้

หากกลยุทธ์ของ Indiana Jones ในการหาหีบคือการตัดสินใจการกระทำถัดไปเมื่อจำเป็น เขาจะทำหน้าที่เหมือน selection sort และจะค้นหาองค์ประกอบที่เล็กที่สุดในบรรดาการกระทำที่เหลือเสมอ เพราะที่นี่คำว่า เล็กที่สุด หมายความว่า "ต้องมาก่อนการกระทำอื่นทั้งหมด" ตามที่ได้กล่าวแล้ว นี่ไม่ใช่วิธีที่มีประสิทธิภาพเพราะ selection sort เป็นอัลกอริทึมกำลังสอง Indiana จะทำได้ดีกว่ามากหากเขาจัดทำแผนล่วงหน้าโดยใช้การเรียงแบบ linearithmic เช่น mergesort แนวทางนี้ของการคำนวณล่วงหน้าเรียกว่า precomputation ในกรณีของแผนการหาหีบ ข้อมูลที่ถูกคำนวณล่วงหน้าไม่ใช่ชุดของขั้นตอนแต่เป็นการจัดเรียงขั้นตอนให้เป็นลำดับที่ถูกต้อง

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

บางวิธีชาร์จแบตเตอรี่โครงสร้างข้อมูลได้มีประสิทธิภาพมากกว่าวิธีอื่น ซึ่งสะท้อนในเวลารันที่ต่างกันของอัลกอริทึมการเรียงต่าง ๆ ตัวอย่างเช่น insertion sort มีประสิทธิภาพน้อยกว่า mergesort และข้อเท็จจริงที่ว่า mergesort เป็นอัลกอริทึมที่ optimal หมายความว่ามีวิธีที่มีประสิทธิภาพที่สุดสำหรับการชาร์จแบตเตอรี่รายการที่เรียงแล้ว แตกต่างจากแบตเตอรี่ไฟฟ้าที่พลังงานใช้ได้เพียงครั้งเดียว แบตเตอรี่ของโครงสร้างข้อมูลมีคุณสมบัติที่ดีคือเมื่อถูกชาร์จแล้วสามารถใช้งานซ้ำได้โดยไม่ต้องชาร์จใหม่ ซึ่งเป็นเหตุผลสำคัญที่สนับสนุนการคำนวณล่วงหน้า สถานการณ์ที่คาดว่าจะใช้โครงสร้างข้อมูลซ้ำ ๆ ให้เหตุผลที่ดีแก่การลงทุนในการคำนวณล่วงหน้าเพราะต้นทุนสามารถเฉลี่ยออกไปในหลายการใช้งาน ในทางกลับกัน แบตเตอรี่โครงสร้างข้อมูลต้องชาร์จให้เต็มจึงจะใช้งานได้ รายการที่เกือบเรียงไม่เพียงพอเพราะไม่รับประกันว่าองค์ประกอบที่เล็กที่สุดจะอยู่ด้านหน้าและอาจให้ผลลัพธ์ผิดพลาด โดยสรุป แบตเตอรี่โครงสร้างข้อมูลมีสองสถานะ: ชาร์จเต็มและมีประโยชน์ หรือไม่

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

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

ทัศนคติสงสัยต่ออนาคตเรียกร้องกลยุทธ์ที่แตกต่างอย่างมากในการจัดตารางการคำนวณ คือกลยุทธ์ที่พยายามเลื่อนการปฏิบัติการที่มีต้นทุนสูงออกไปจนสุดเท่าที่จะทำได้ โดยหวังว่าบางสิ่งอาจเกิดขึ้นทำให้การปฏิบัติการนั้นล้าสมัยและประหยัดเวลา (และทรัพยากรอื่น ๆ) ในชีวิตจริง พฤติกรรมเช่นนี้เรียกว่า "เลื่อน" แต่ในวิทยาการคอมพิวเตอร์เรียกว่า lazy evaluation Lazy evaluation สามารถประหยัดการคำนวณได้เมื่อข้อมูลที่ได้จากการคำนวณที่ถูกเลื่อนนั้นไม่ถูกใช้ ในกรณีผจญภัยของ Indiana Jones มักเกิดขึ้นบ่อยครั้งที่แผนเริ่มต้นต้องเปลี่ยนหรือยกเลิกเพราะเหตุการณ์ที่ไม่คาดคิดหรือความยุ่งยาก ในกรณีเช่นนี้ ความพยายามทั้งหมดที่ใช้ในการวางแผนอาจสูญเปล่าและอาจประหยัดได้หากไม่วางแผนตั้งแต่แรก

ในขณะที่ผู้สนับสนุนการคำนวณล่วงหน้าอาจมีคติว่า “งานที่ทำก่อนช่วยประหยัดได้หลายเท่า” หรือ “นกตัวแรกได้เหยื่อ” ผู้สนับสนุน lazy evaluation อาจตอบกลับว่า “จริง แต่หนูตัวที่สองได้ชีส” แม้ว่า lazy evaluation จะมีเสน่ห์เพราะสัญญาว่าไม่เสียงาน แต่ก็มีปัญหาเมื่อต้องทำการกระทำที่หลีกเลี่ยงไม่ได้ซึ่งใช้เวลานานกว่าที่จะทำภายใต้การคำนวณล่วงหน้า หรือเลวร้ายกว่านั้น ใช้เวลานานกว่าที่มีอยู่ โดยเฉพาะเมื่อการกระทำที่ถูกเลื่อนไว้หลายอย่างมีกำหนดพร้อมกัน อาจเกิดปัญหาทรัพยากรอย่างร้ายแรง ดังนั้นกลยุทธ์ที่สมเหตุสมผลกว่าคือการกระจายงานให้เท่ากันตลอดเวลา แม้ว่านี่อาจเสียงานบางส่วนสำหรับการคำนวณล่วงหน้า แต่มันก็หลีกเลี่ยงวิกฤตที่กลยุทธ์ lazy evaluation อาจก่อให้เกิด