การจัดเรียงและค้นหาข้อมูล

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

การจัดเรียงข้อมูล

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

 

 

ตัวอย่างสถานการณ์

ให้เรียงลำดับตัวเลขในตารางด้านล่างนี้ จากน้อยไปหามาก

84

96 8 77 92 35 61 90 50 56
85 60 9 62 13 58 42 54 44

86

 

โดยทั่วไปการเรียงลำดับจำนวนเต็ม อาจใช้การจัดเรียงข้อมูลได้ 2 แบบ คือ

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

ภาพแสดงขั้นตอนการทำงานของการเรียงลำดับแบบเลือก โดยสีเหลือง คือ เรียงเรียบร้อยแล้ว , สีแดง คือ ค่าที่น้อยที่สุดในปัจจุบัน และสีฟ้า คือ ค่าที่กำลังพิจารณา

 

2. การเรียงลำดับแบบแทรก (Insertion sort)
การเรียงลำดับแบบแทรก เป็นขั้นตอนวิธีการเรียงลำดับอย่างง่าย ทำงานโดยจะแบ่งข้อมูลในรายการเป็นสองส่วนคือส่วนที่เรียงแล้วและส่วนที่ยังไม่เรียง แน่นอนว่าในตอนเริ่มแรกส่วนที่เรียงแล้วก็จะมีอย่างน้อยหนึ่งตัว และจะเริ่มหยิบข้อมูลตัวหนึ่งของส่วนที่ยังไม่เรียงมาเปรียบเทียบเพื่อหาตำแหน่งที่เหมาะสมในการแทรกลงในข้อมูลส่วนที่เรียงแล้ว ลักษณะเดียวกับการเรียงไพ่ในมือ ดังนั้นการเรียงลำดับแบบแทรกจึงไม่เหมาะในการทำงาน ในรายการที่มีจำนวนสมาชิกมาก ๆ

ภาพแสดงขั้นตอนการทำงานของการเรียงลำดับแบบแทรก

 

 

 

 

กิจกรรม

ให้นักเรียนแสดงขั้นตอนวิธีเรียงข้อมูลแบบเลือก และแบบแทรก

 

 

 

 

 

 

อ้างอิง

สถาบันส่งเสริมการสอนวิทยาศาสตร์และเทคโนโลยี, “เทคโนโลยี(วิทยาการคำนวณ)”, โรงพิมพ์แห่งจุฬาลงกรณ์มหาวิทยาลัย, ศูนย์หนังสือแห่งจุฬาลงกรณ์มหาวิทยาลัย, 2561 หน้า 51

myalgo.wordpress.com, “Selection Sort”, https://myalgo.wordpress.com/2010/09/02/selection-sort/, สืบค้นวันที่ 31 พ.ค. 61

วิกิพีเดีย สารานุกรมเสรี, “การเรียงลำดับแบบเลือก”, https://th.wikipedia.org/wiki/%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B9%80%E0%B8%A3%E0%B8%B5%E0%B8%A2%E0%B8%87%E0%B8%A5%E0%B8%B3%E0%B8%94%E0%B8%B1%E0%B8%9A%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B9%80%E0%B8%A5%E0%B8%B7%E0%B8%AD%E0%B8%81, สืบค้นวันที่ 31 พ.ค. 61

วิกิพีเดีย สารานุกรมเสรี, “การเรียงลำดับแบบแทรก”, https://th.wikipedia.org/wiki/%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B9%80%E0%B8%A3%E0%B8%B5%E0%B8%A2%E0%B8%87%E0%B8%A5%E0%B8%B3%E0%B8%94%E0%B8%B1%E0%B8%9A%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B9%81%E0%B8%97%E0%B8%A3%E0%B8%81, สืบค้นวันที่ 31 พ.ค. 61

เอกราช เจริญผล, “การจัดเรียงข้อมูล (Sorting)”, http://aekaratdatastructure.blogspot.com/2013/01/insertion-sort.html, สืบค้นวันที่ 31 พ.ค. 61