ผู้คิดค้นอัลกอริทึม Quicksort ‘โทนี ฮอร์’ เสียชีวิตแล้ว ข้อผิดพลาด ‘หนึ่งพันล้านดอลลาร์’ ที่เขาสร้างขึ้นส่งผลต่อโลกการเขียนโปรแกรมอย่างไร?

บิดาแห่งอัลกอริทึม Quicksort ผู้ได้รับรางวัล Turing Award เสียชีวิตแล้วด้วยวัย 92 ปี

ในสาขาวิทยาการคอมพิวเตอร์ เกือบไม่มีใครสามารถหลีกเลี่ยงอัลกอริทึมการเรียงลำดับแบบเร็ว (Quicksort) ได้ ในฐานะหนึ่งในอัลกอริทึมการเรียงลำดับที่ใช้กันอย่างแพร่หลายที่สุดทั่วโลก มันถูกผนวกรวมไว้ในไลบรารีมาตรฐานของภาษาโปรแกรมหลักเกือบทั้งหมด ตั้งแต่ C, Java ไปจนถึง Python

อย่างไรก็ตาม Quicksort เป็นเพียงจุดเริ่มต้นของเส้นทางวิชาการที่ยาวนานและโดดเด่นของโทนี่ โฮร์ ในฐานะผู้ได้รับรางวัล Turing Award ปี 1980 เขาได้เสนอตรรกะของโฮร์ (Hoare Logic) สำหรับการตรวจสอบความถูกต้องของโปรแกรมอย่างเป็นทางการ สร้างแบบจำลองกระบวนการเรียงลำดับการสื่อสาร (CSP) ที่มีอิทธิพลอย่างลึกซึ้งต่อการออกแบบภาษา Go พร้อมกันนี้ เขายังมีอิทธิพลอย่างมากต่อภาษาโปรแกรมรุ่นหลัง เช่น Java, C++ เนื่องจากได้นำเสนอแนวคิดการอ้างอิงว่าง (null reference) ซึ่งเขาเรียกตัวเองว่า “ความผิดพลาดพันล้านดอลลาร์”

อัลกอริทึมที่กำเนิดในมอสโก

เรื่องราวของ Quicksort เริ่มต้นในปี 1959 ขณะนั้น โฮร์อายุ 25 ปี ในฐานะนักเรียนแลกเปลี่ยน เขากำลังศึกษาการแปลภาษาเครื่องที่มหาวิทยาลัยแห่งรัฐมอสโก

โครงการที่เขาเข้าร่วมต้องการเรียงลำดับคำในประโยคภาษารัสเซีย เพื่อค้นหาบนเทปแม่เหล็กที่เก็บพจนานุกรมรัสเซีย-อังกฤษ การเรียงลำดับเป็นขั้นตอนแรก โฮร์คิดถึงอัลกอริทึมการเรียงลำดับแบบฟอง (Bubble Sort) ในตอนแรก

หลักการของ Bubble Sort นั้นเรียบง่ายและตรงไปตรงมา: วนลูปผ่านรายการองค์ประกอบ เปรียบเทียบองค์ประกอบที่อยู่ติดกันและสลับตำแหน่งที่ผิดลำดับ จนกว่ารายการทั้งหมดจะเรียงลำดับ หากในการวนลูปครั้งหนึ่งไม่มีการสลับเกิดขึ้น แสดงว่าการเรียงลำดับเสร็จสิ้น แต่โฮร์ตระหนักได้อย่างรวดเร็วว่า ความซับซ้อนของเวลา O(n²) นั้นไม่มีประสิทธิภาพเพียงพอเมื่อประมวลผลข้อมูลขนาดใหญ่

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

หลังจากกลับถึงอังกฤษ เพื่อนร่วมงานสงสัยในวิธีการใหม่ของเขา และพนันหกเพนนีว่า มันไม่สามารถเร็วกว่าอัลกอริทึม Shell Sort ที่ได้รับความนิยมในขณะนั้นได้ Shell Sort เป็นเวอร์ชันปรับปรุงของ Insertion Sort โดยปรับปรุงประสิทธิภาพผ่านการกำหนดระยะห่างเพื่อจัดกลุ่มและเรียงลำดับ จากนั้นค่อยๆ ลดระยะห่างลง ความซับซ้อนของเวลาอยู่ระหว่าง O(n log n) ถึง O(n²)

โฮร์ใช้เวลาช่วงบ่ายหนึ่งวันในการปรับแต่งรายละเอียดของ Quicksort และชนะการพนัน ข้อเท็จจริงพิสูจน์ว่า ความซับซ้อนของเวลาเฉลี่ยของ Quicksort คือ O(n log n) และช้ากว่า Shell Sort เฉพาะในกรณีที่หายากมากเท่านั้น นอกจากนี้ ในฐานะอัลกอริทึมการเรียงลำดับแบบในสถานที่ (in-place) มันต้องการพื้นที่เสริมเพียง O(log n) และการปรับตัวที่ดีกับกลไกแคชของคอมพิวเตอร์สมัยใหม่ (Temporal Locality และ Spatial Locality) ทำให้มันมักจะทำงานได้เร็วกว่าในทางปฏิบัติ

ตั้งแต่ทศวรรษ 1960 Quicksort ได้กลายเป็นเนื้อหาหลักของการศึกษาวิทยาการคอมพิวเตอร์ และเป็นรากฐานประสิทธิภาพของซอฟต์แวร์และระบบฐานข้อมูลนับไม่ถ้วน ส่วนการพนันหกเพนนีนั้นจ่ายจริงหรือไม่ โฮร์ระลึกในบั้นปลายชีวิตว่า เขาจำไม่ได้แล้ว

ในปี 1961 โฮร์ใช้คุณลักษณะการเรียกซ้ำของภาษาโปรแกรม Algol 60 ในการฝึกอบรมภาษาโปรแกรมนั้น เพื่อนำ Quicksort ไปปฏิบัติ รหัสที่เกี่ยวข้องได้รับการตีพิมพ์ใน “The Computer Journal” ในปี 1962 กลายเป็นบทความวิชาการฉบับที่สามของเขา และวางรากฐานที่สำคัญสำหรับเส้นทางวิชาการของเขา

“ความผิดพลาดพันล้านดอลลาร์”

Quicksort ทำให้โฮร์มีชื่อเสียงโด่งดัง แต่ผลงานของเขาไม่ได้หยุดอยู่แค่นั้น

ในปี 1969 เขาเสนอตรรกะของโฮร์ (Hoare Logic) ซึ่งวางรากฐานสำหรับระบบที่เป็นทางการสำหรับการพิสูจน์ความถูกต้องของโปรแกรมอย่างเคร่งครัด และส่งเสริมการวิจัยความน่าเชื่อถือและความปลอดภัยของซอฟต์แวร์อย่างมาก

ในปี 1978 เขาเสนอแบบจำลองกระบวนการเรียงลำดับการสื่อสาร (CSP) ซึ่งให้กรอบสำหรับอธิบายการโต้ตอบของกระบวนการในระบบพร้อมกัน แบบจำลองนี้เป็นแรงบันดาลใจโดยตรงสำหรับการออกแบบระบบพร้อมกันของภาษา Go ที่มี channel เป็นแกนกลาง

ในปี 1980 โฮร์ได้รับรางวัล Turing Award เนื่องจาก “การมีส่วนร่วมพื้นฐานต่อการกำหนดนิยามและการออกแบบภาษาโปรแกรม” คำประกาศรางวัลชี้ให้เห็นว่า ข้อบกพร่องของภาษาโปรแกรมเองเป็นสาเหตุสำคัญที่ทำให้ต้นทุนซอฟต์แวร์สูง คุณภาพไม่ดี และมีช่องโหว่ด้านความปลอดภัย

ในการบรรยายรับรางวัล Turing Award และในบทความปี 1973 “Hints on Programming Language Design” โฮร์เน้นย้ำเสมอว่าความเรียบง่ายและความสง่างามเป็นกุญแจสำคัญในการรักษาซอฟต์แวร์ให้อยู่ภายใต้การควบคุมของสติปัญญามนุษย์

อย่างไรก็ตาม โฮร์ยังได้ออกแบบที่ก่อให้เกิดข้อโต้แย้งที่มีอิทธิพลลึกซึ้งอีกด้วย ในปี 1965 ขณะออกแบบภาษา ALGOL W เพื่อความสะดวกในการแสดงสถานะ “ไม่มีค่า” เขาได้แนะนำการอ้างอิงว่าง (null reference) เนื่องจากใช้งานง่าย แนวคิดนี้จึงถูกนำไปใช้อย่างกว้างขวางในภาษาต่างๆ มากมายในภายหลัง เช่น Java, C#, C++ แต่ก็ทำให้เกิดข้อยกเว้นตัวชี้ว่าง (Null Pointer Exception) ระบบขัดข้อง และช่องโหว่ด้านความปลอดภัยนับไม่ถ้วนตามมา

ในปี 2009 โฮร์อายุ 75 ปี ได้สะท้อนคิดอย่างเปิดเผยในการบรรยายสาธารณะครั้งหนึ่ง:

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

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

จากนักวิชาการคลาสสิกสู่ผู้บุกเบิกคอมพิวเตอร์

เส้นทางชีวิตของโฮร์ก็มีความพิเศษเช่นกัน เขาเกิดในปี 1934 ที่ซีลอนของอังกฤษ (ปัจจุบันคือศรีลังกา) และเริ่มต้นศึกษาวิชาคลาสสิกและปรัชญาที่มหาวิทยาลัยอ็อกซ์ฟอร์ด หลังจากสำเร็จการศึกษา ในระหว่างรับราชการทหาร เขาได้เรียนภาษารัสเซีย ซึ่งสร้างโอกาสให้เขาเดินทางไปมอสโกเพื่อศึกษาและประดิษฐ์อัลกอริทึม Quicksort ในเวลาต่อมา

หลังจากปลดประจำการแล้ว เพื่อศึกษาตรรกะรูปแบบในวิชาคลาสสิกอย่างลึกซึ้ง โฮร์กลับไปที่อ็อกซ์ฟอร์ดเพื่อศึกษาปริญญาโทด้านสถิติ และได้สัมผัสกับภาษา Mercury Autocode เป็นครั้งแรก ก้าวเข้าสู่โลกแห่งการเขียนโปรแกรมอย่างเป็นทางการ

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

บทความวิทยาศาสตร์ฉบับแรกของโฮร์ เขียนด้วยภาษารัสเซียในช่วงที่อยู่มอสโก และตีพิมพ์ในนิตยสาร “Machine Translation” ของสหภาพโซเวียต เนื่องจากการถอดเสียงภาษารัสเซีย นามสกุล “Hoare” ของเขาต้องค้นหาภายใต้รายการ “C” หรือ “K” ในดัชนีบทความ

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

แต่เมื่อเขากลับไปอังกฤษเพื่อสัมภาษณ์ ฝ่ายทรัพยากรบุคคลแจ้งว่า: เนื่องจากเขาไม่มีปริญญาด้านวิทยาศาสตร์ เขาจะไม่มีวันสามารถเป็นข้าราชการวิทยาศาสตร์ประจำได้

พวกเขาเสนอจ้างเขาในตำแหน่ง “เจ้าหน้าที่เทคนิคชั่วคราว” เท่านั้น ซึ่งตำแหน่งต่ำกว่าที่สัญญาไว้เดิมสองถึงสามระดับ และไม่มีโอกาสเลื่อนตำแหน่ง โฮร์ปฏิเสธทันที ห้าปีต่อมา โครงการแปลภาษาเครื่องนั้นล้มเหลวในที่สุด

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

อย่างไรก็ตาม รถบรรทุกขับออกจากมอสโกได้เพียง 30 ไมล์ คันเร่งก็เกิดขัดข้อง การตรวจสอบพบว่าส่วนของก้านต่อหลุดออก พวกเขาต้องถอดชิ้นส่วนจากตัวรถมาประกอบเป็นชิ้นส่วนชั่วคราวทดแทน แต่แผนนี้มีปัญหาอันตรายร้ายแรง: ตรรกะของคันเร่งกลับด้าน – ต้องการเร่งความเร็วต้องปล่อยแป้นเหยียบ ต้องการเบรกกลับต้องเหยียบลง

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

หลังจากกลับจากมอสโก อาชีพการงานของโฮร์เคลื่อนไหวระหว่างภาคอุตสาหกรรมและภาควิชาการ

ในปี 1960 เขาเข้าร่วมบริษัท Elliott Brothers นำทีมสร้างคอมไพเลอร์เชิงพาณิชย์ตัวแรกสำหรับภาษาโปรแกรม ALGOL 60 และต่อมาได้เป็นหัวหน้านักวิทยาศาสตร์ของบริษัท

ในทางตรงกันข้าม แนชจาก Elliott เสนอเงินเดือนประจำปีมาตรฐานสำหรับโปรแกรมเมอร์จบใหม่ให้เขา – 800 ปอนด์ พร้อมเงินเพิ่มภาษารัสเซีย 100 ปอนด์ แนชกล่าวกับโฮร์ในภายหลังว่า: “ฉันคิดว่าสิ่งที่ดีที่สุดที่ฉันทำให้ Elliott คือการรับคุณเข้ามาทำงาน”

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

ครั้งหนึ่งขณะย้ายบ้านและจัดเอกสาร เขาพบบทความปี 1967 ของบ็อบ ฟลอยด์ (Bob Floyd) ที่ชื่อ “Assigning Meanings to Programs” ฟลอยด์เสนอวิธีการเพิ่มข้อความยืนยัน (assertion) บนผังงานโปรแกรม ทำให้สามารถพิสูจน์ว่าโปรแกรมสอดคล้องกับข้อกำหนดได้

โฮร์ก้าวไปอีกสองขั้นบนพื้นฐานนี้:

ประการแรก เขาทิ้งผังงาน และพัฒนาระบบตรรกะสำหรับให้เหตุผลโดยตรงกับคำสั่งโปรแกรม ซึ่งแกนกลางคือ “Hoare Triple” ที่ตั้งชื่อตามเขาในภายหลัง

ประการที่สอง เขาเสนอว่าระบบสัจพจน์นี้เองสามารถใช้เป็นวิธีที่เป็นนามธรรมในการบันทึกความหมายของภาษาโปรแกรม

บทความปี 1969 “An Axiomatic Basis for Computer Programming” กลายเป็นหนึ่งในบทความที่มีอิทธิพลมากที่สุดในสาขาทฤษฎีการเขียนโปรแกรม

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

หนึ่งในผลงานทฤษฎีที่สำคัญที่สุดของโฮร์ – แบบจำลองระบบพร้อมกัน CSP เกิดจากความล้มเหลวครั้งหนึ่ง

ในระหว่างทำงานที่ Elliott Brothers เขารับผิดชอบการออกแบบระบบปฏิบัติการสำหรับ Elliott 503 Mark II แต่โครงการสุดท้ายไม่สามารถส่งมอบได้ ซึ่งนำไปสู่การสิ้น

⚠️ หมายเหตุ: เนื้อหาได้รับการแปลโดย AI และตรวจสอบโดยมนุษย์ หากมีข้อผิดพลาดโปรดแจ้ง