การค้นหาข้อมูลแบบลำดับขั้นตอนแตกต่างจากการค้นหาข้อมูลแบบทวิภาคอย่างไรจงอธิบาย

ในบทเรียนนี้จะได้เรียนรู้กับขั้นตอนวิธีพื้นฐานในการจัดเรียงข้อมูล (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/, สืบค้นวันที่ 31 พ.ค. 61

วิกิพีเดีย สารานุกรมเสรี, “การเรียงลำดับแบบแทรก”, https://th.wikipedia.org/, สืบค้นวันที่ 31 พ.ค. 61

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

การค้นหาข้อมูล

การค้นหาข้อมูลที่มีประสิทธิภาพนั้น ขึ้นอยู่กับหลักการค้นหา รวมถึงขั้นตอนของการค้นหานั้น การค้นหาข้อมูลพื้นฐานมีหลากหลายวิธี เช่น การค้นหาข้อมูลแบบลำดับ การค้นหาข้อมูลแบบทวิภาค และการค้นหาข้อมูลแบบแฮชชิง

การใช้เทคนิคการค้นหาข้อมูลแบบใดต้องดูลักษณะของงาน ซึ่งจะช่วยให้เราสามารถตัดสินใจเลือกเทคนิคการค้นหาข้อมูลที่เหมาะสมได้

การค้นหาข้อมูลแบบลำดับ(Sequential Search)

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

1.พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์(Successful Search)

2. ไม่พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์ (Unsuccessful Search)

การค้นหาข้อมูลแบบทวิภาค (Binary Serach)

การค้นหาข้อมูลแบบทวิภาค เหมาะสำหรับค้นหาข้อมูลที่มีการเรียงลำดับอยู่แล้ว โดยการค้นหาแต่ละรอบจะลดขอบเขตการค้นหาลงทีละครึ่ง

การค้นหาข้อมูลแบบทวิภาคมีประสิทธิภาพดีมากและเป็นแนวคิด หลักในการพัฒนาระบบฐานข้อมูล หลังพิจารณาข้อมูลแต่ละครั้ง ขอบเขตของดัชนีที่เป็นไปได้จะลดลงประมาณครึ่งหนึ่ง ถ้าข้อมูลในรายการมีจำนวน n ตัว จำนวนรอบที่ต้องทํางานจะเท่ากับจําานวนครั้งในการลดค่าขอบเขตที่เป็นไปได้จาก n ทีละครึ่งจนเหลือค่าเท่ากับ 1 ซึ่งค่าดังกล่าวสอดคล้อง กับฟังก์ชันลอการิทึม (logarithm) ฐาน 2 ของ n ดังนั้นความซับซ้อนของ ขั้นตอนวิธีการค้นหาแบบทวิภาคจะแปรผันตรงกับ log2 n นั่นคือเรา สามารถเขียนว่าการค้นหาแบบทวิภาคมีความซับซ้อนเป็น O(log2 n)

เทคนิคการค้นหาข้อมูลด้วยวิธีนี้

1. กำหนดข้อมูลที่ต้องการค้นหาและทำการเรียงข้อมูลตามความต้องการ เรียงจากมากไปน้อย หรือจากน้อยไปมากก็ได้

2. ทำการแบ่งข้อมูลออกเป็น 2 ส่วน แล้วทำการหาค่ากลาง

3. เมื่อทราบแล้วว่าค่าของคีย์ฟิลด์อยู่ครึ่งแรกหรือครึ่งหลังแล้ว ก็จะนำข้อมูลในครึ่งดังกล่าวทำการหาค่ากลางอีก ทำแบบนี้ไปเรื่อย ๆ จนกระทั้งได้ข้อมูลที่ต้องการ หรือจนกระทั่งไม่สามารถแบ่งข้อมูลได้อีก

ตัวอย่างการค้นหา

เปรียบเทียบระหว่าง Sequential Search และ Binary Search

การเปรียบเทียบครั้งนี้ จะใช้ Binary Search เป็นตัวอ้างอิง ซึ่งเราจะแบ่งออกเป็น 2 ประเภท คือ

1. Best Case Binary Search

2.Worst Case Binary Search

จะเห็นได้ว่า Binary Search สามารถหาข้อมูลที่ต้องการได้เร็วกว่า Sequential Search เมื่อมีจำนวนข้อมูลจำนวนมาก แต่ถ้าหากมีข้อมูลน้อยๆ และสิ่งที่ต้องการหานั้นอยู่เป็นต้นๆก็จำทำให้การหาแบบ Sequential Search เร็วกว่า ดังกราฟ

โดยที่ n = Sequential Search
log(n) = Binary Search

ที่มา : http://cs60052016.blogspot.com/2016/10/sequential-search-vs-binary-search.html