บทที่ 7 การจัดเรียงและค้นหาข้อมูล
การจัดเรียงและค้นหาข้อมูล
ในบทเรียนนี้จะได้เรียนรู้กับขั้นตอนวิธีพื้นฐานในการจัดเรียงข้อมูล
(Sort)
และการค้นหาข้อมูล (Search) ซึ่งเป็นกิจกรรมที่สัมพันธ์กันที่ใช้ในการแก้ปัญหาที่พบบ่อยในชีวิตประจำวัน
การจัดเรียงข้อมูล
การจัดเรียงข้อมูลเป็นสิ่งที่พบอยู่เสมอ
เมื่อต้องการประมวลผลข้อมูลเป็นจำนวนมาก เช่น ครูตรวจข้อสอบของนักเรียน
และต้องการบันทึกคะแนนลงสมุดบันทึกคะแนนนักเรียนที่มีการเรียงเลขที่เอาไว้
การเรียงลำดับข้อมูลด้วยเงื่อนไขที่เหมาะสมจะทำให้การค้นหาข้อมูลทำได้อย่างมีประสิทธิภาพ
ตัวอย่างสถานการณ์
ให้เรียงลำดับตัวเลขในตารางด้านล่างนี้
จากน้อยไปหามาก
โดยทั่วไปการเรียงลำดับจำนวนเต็ม
อาจใช้การจัดเรียงข้อมูลได้ 2 แบบ คือ
1. การจัดเรียงแบบเลือก (Selection
sort)
การเรียงลำดับแบบเลือก
เป็นขั้นตอนวิธีการเรียงลำดับอย่างง่ายโดยใช้วิธีการเปรียบเทียบ
ทำงานโดยการหาค่าเหมาะสมที่สุด (ค่ามากสุดหรือน้อยสุด)
ที่อยู่ในรายการส่วนที่ยังไม่เรียงและนำค่าเหมาะที่สุดนั้นมาต่อท้ายของส่วนที่เรียงแล้ว
ภาพแสดงขั้นตอนการทำงานของการเรียงลำดับแบบเลือก โดยสีเหลือง คือ เรียงเรียบร้อยแล้ว , สีแดง คือ
ค่าที่น้อยที่สุดในปัจจุบัน และสีฟ้า คือ ค่าที่กำลังพิจารณา
2. การเรียงลำดับแบบแทรก (Insertion sort)
การเรียงลำดับแบบแทรก
เป็นขั้นตอนวิธีการเรียงลำดับอย่างง่าย
ทำงานโดยจะแบ่งข้อมูลในรายการเป็นสองส่วนคือส่วนที่เรียงแล้วและส่วนที่ยังไม่เรียง
แน่นอนว่าในตอนเริ่มแรกส่วนที่เรียงแล้วก็จะมีอย่างน้อยหนึ่งตัว
และจะเริ่มหยิบข้อมูลตัวหนึ่งของส่วนที่ยังไม่เรียงมาเปรียบเทียบเพื่อหาตำแหน่งที่เหมาะสมในการแทรกลงในข้อมูลส่วนที่เรียงแล้ว
ลักษณะเดียวกับการเรียงไพ่ในมือ ดังนั้นการเรียงลำดับแบบแทรกจึงไม่เหมาะในการทำงาน
ในรายการที่มีจำนวนสมาชิกมาก ๆ
ภาพแสดงขั้นตอนการทำงานของการเรียงลำดับแบบแทรก
ไม่มีความคิดเห็น:
แสดงความคิดเห็น