Majority
การหาตัวหมู่มากในอาเรย์ทำได้หลายวิธี ในที่นี้ขอเขียนให้ดู 6 วิธี
- วิธีที่ 1: ลุยนับไปทีละตัวว่ามีปรากฏในอาเรย์กี่ตัว เมื่อใดพบตัวที่มีจำนวนเกินครึ่งก็รีบคืนผล แต่ละลองหมดแล้วไม่พบ ก็แสดงว่าไม่มีตัวหมู่มาก
- วิธีที่ 2: อาศัยการเรียงลำดับข้อมูลอาเรย์เสียก่อน ทำให้ตัวที่เหมือนอยู่ติดกัน จึงสามารถหาจำนวนที่ซ้ำกันได้ง่ายขึ้นด้วยการวิ่งในอาเรย์เพียงรอบเดียว แต่วิธีนี้ต้องเสียเวลา sort
- วิธีที่ 3: เริ่มใด้วยการ sort เหมือนวิธีที่ 2 แต่ขอนับเฉพาะตัวตรงกลางอาเรย์ (หลังการ sort) ก็พอ เพราะถ้ามีตัวหมู่มาก ตัวนั้นก็ต้องเป็นตัวมัธยฐานด้วย
- วิธีที่ 4: ใช้ divide and conquer อยากให้ลองทำความเข้าใจดูเองว่า ทำอะไร
- วิธีที่ 5: เหมือนวิธีที่ 4 คือลองทำความเข้าใจดูเองว่า ทำอะไร
- วิธีที่ 6: อาศัยการสุ่มเลือกแล้วนำมานับ ถ้านับแล้วเป็นตัวหมู่มาก ก็จบเพราะพบแล้ว แต่ถ้าสุ่มแล้วนับแต่ไม่ใช่ ก็ลองใหม่ ทำแบบนี้สัก 30 หน ได้วิธีที่มั่นใจมากๆๆๆๆ ว่าทำงานได้ถูกต้อง
เรานำทั้งหกวิธีมาทดลองกับข้อมูลในอาเรย์ 4 แบบดังนี้ (ลองดูว่าแต่ละวิธีมีข้อดีข้อเสียอย่างไร กับข้อมูลแต่ละแบบ)
(อย่าลืมอ่านข้อแนะนำในการตีความผลการทดลอง)
data1
อาเรย์มีตัวหมู่มาก โดยลำดับที่ปรากฎในอาเรย์เป็นแบบสุ่ม
data2
อาเรย์มีตัวหมู่มาก โดยตัวหมู่มากทั้งหมดอยู่ทางขวาของอาเรย์
data3
อาเรย์ไม่มีตัวหมู่มาก ข้อมูลทุกตัวต่างกันหมด
data4
อาเรย์ไม่มีตัวหมู่มาก ข้อมูลมีลักษณะสลับกันสองตัว 0,1,0,1,0,1,...,0,1 แล้วตามด้วย 2
สมชาย ประสิทธิ์จูตระกูล