รบกวนช่วยหาคำตอบด้วยครับ

[Dido]

การชั่งของครั้งละ 2 ชิ้น(ที่ละก้อน)เพื่อเปรียบเทียบและจัดเรียงตามลำดับจากน้อยไปมากโดยให้การชั่งได้จำนวนน้อยที่สุดจะทำอย่างไร ?
คำถาม
1. ถ้าชั่งที่ละ 2 ก้อนต้องทำอย่างไรเพื่อให้ได้จำนวนครั้งที่น้อยที่สุด ?
2. ถ้ามี n ก้อน โดยเงื่อนไขที่โจทย์กำหนดจะมีจำนวนครั้งเป็นฟังก์ชันของตัวแปร n อย่างไร ?

[tunococ]

ผมจะตอบรวม ๆ สองข้อละกันนะครับ

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

วิธีที่นิยมใช้ในการเรียงข้อมูล (ที่มี domain เป็นเซตอนันต์) ที่ใช้เวลาน้อยที่สุด 3 แบบคือ
1. HeapSort
2. QuickSort
3. MergeSort

แต่ละตัวก็มีข้อดีข้อเสียต่างกันครับ โดยส่วนตัวแล้ว ผมเชื่อว่า MergeSort ใช้จำนวนการเปรียบเทียบน้อยที่สุดในสามวิธีนี้ครับ แต่ใช้หน่วยความจำเพิ่มเติมมากที่สุด

สำหรับ MergeSort จำนวนครั้งในการเปรียบเทียบ (ในกรณีที่แย่ที่สุด) เป็นฟังก์ชันดังนี้
\[f(n) = n + 2f\left(\frac{n}{2}\right)\]\[f(n) = \Theta(n \log n)\]
และในกรณีที่ดีที่สุด ก็จะเป็น
\[f(n) = 1 + 2f\left(\frac{n}{2}\right)\]\[f(n) = \Theta(n)\]

ส่วน HeapSort ในกรณีที่แย่ที่สุด จำนวนครั้งในการเปรียบเทียบจะเยอะกว่า คือ (ประมาณเอานะครับ)
\[f(n) = n \sum_{i=1}^{\log_2(n/2)} \frac{i}{2^i} + \sum_{i=1}^{n - 1}i \log_2 i\]\[f(n) = \Theta(n \log n)\]

ส่วนกรณีที่ดีที่สุด จำนวนการเปรียบเทียบคือ (ประมาณ)
\[f(n) = n \sum_{i=1}^{\log_2(n/2)} \frac{i}{2^i}\]\[f(n) = \Theta(n)\]

แล้วก็ QuickSort จะมีอยู่หลายเวอร์ชั่น (อันนี้แจกแจงยาก ขอสรุปเลยละกัน) ถ้าเป็นแบบ Randomized QuickSort กรณีแย่สุดจะได้
\[f(n) = \Theta(n^2)\]แต่กรณีที่ดีที่สุด จะเป็น\[f(n) = \Theta(n)\]

แต่ถ้าเป็น QuickSort แบบ Median-of-Median-of-Five กรณีแย่ที่สุดจะได้\[f(n) = \Theta(n \log n)\]ส่วนกรณีที่ดีที่สุดก็จะเป็น \[f(n) = \Theta(n)\]

ในการเขียนเป็นโปรแกรมคอมพิวเตอร์ เนื้อที่ในหน่วยความจำก็มีผลครับ

MergeSort ใช้หน่วยความจำเพิ่มอีก \(\Theta(n)\)
HeapSort ไม่ใช้หน่วยความจำเพิ่มเติม
Randomized QuickSort ใช้หน่วยความจำเพิ่มอีก \(O(n), \Omega(\log n)\)
Median-of-Median-of-Five QuickSort ใช้หน่วยความจำเพิ่มอีก \(\Theta(\log n)\)

วิธีทำ MergeSort

เริ่มจาก Merge ก่อนครับ สมมติว่ามีลำดับของข้อมูลที่เรียงอยู่แล้วสองชุด แต่ละชุดมี \(n\) ตัว เราจะมารวมกันให้เป็นลำดับของข้อมูลที่เรียงถูกต้อง ความยาว \(2n\) ได้อย่างไร?

อันนี้ถือว่าคิดกันเองได้ละกันครับว่า กรณีที่แย่ที่สุด จะต้องเปรียบเทียบ \(2n - 1\) ครั้ง

เราจึงรู้ว่า \[h(2n) = 2n\]เมื่อ \(h(2n)\) คือจำนวนการเปรียบเทียบที่เกิดขึ้นในการรวมข้อมูลที่เรียงแล้ว 2 ชุด

ลองไปคิดเล่น ๆ ละกันนะครับ ว่า Induction Proof ต่อไปนี้ ทำยังไง
Basis ข้อมูล 1 ตัวเป็นข้อมูลที่เรียงอยู่แล้ว
Fact ถ้ามีข้อมูล \(n\) ตัว สองชุดที่เรียงอยู่แล้ว จะสามารถต่อกันให้เป็นข้อมูล \(2n\) ตัวที่เรียง ได้ในการเปรียบเทียบไม่เกิน \(2n - 1\) ครั้ง
Hypothesis สามารถเรียงข้อมูล \(2^m\) ตัวได้ โดยใช้การเปรียบเทียบไม่เกิน \(m 2^m\) ครั้ง