Sequential Search คืออะไร
Sequential Search หรือ Linear Search คือ การหาข้อมูลแบบเป็นลำดับขั้นตอน โดยจะค้นหาตั้งแต่ตัวแรกเรียงลำดับไปทีละตัวจนกว่าจะพบข้อมูลที่ต้องการ หรือเปรียบเทียบไปจนถึงตัวสุดท้าย การค้นหาวิธีนี้เป็นวิธีที่ง่ายที่สุด อัลกอริทึ่มในการค้นหาไม่ซับซ้อนสามารถใช้กับข้อมูลที่เรียงลำดับแล้วหรือข้อมูลที่ยังไม่ได้เรียงลำดับก็ได้ โดยผลลัพธ์จากการค้นหาข้อมูลจะมีความเป็นไปได้อยู่ 2 แบบ คือ
1.พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์(Successful Search)
ตัวอย่างการค้นหา
2. ไม่พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์ (Unsuccessful Search)
ตัวอย่างการค้นหา
Binary Search คืออะไร
Binary Search คือ การค้นหาที่ใช้ได้กับชุดข้อมูลที่มีการเรียงลำดับไว้แล้วเท่านั้น หลักการค้นหาเริ่มด้วยการนำคีย์ไปเปรียบเทียบกับค่ากลางของข้อมูลชุดนั้นถ้าคีย์ไปเปรียบเทียบกับค่ากลางของครึ่งชุดข้อมูลที่มีค่าน้อย ถ้าค่าคีย์มากกว่าก็ให้นำไปเปรียบเทียบกับค่ากลางของครึ่งชุดข้อมูลที่มีค่ามาก ทำเช่นนี้เรื่อยไปจนพบข้อมูลที่เท่ากับคีย์หรือจนกระทั่งหมดข้อมูลที่จะเปรียบเทียบ
เทคนิคการค้นหาข้อมูลด้วยวิธีนี้
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 |
การจัดเรียงลำดับข้อมูล (Sorting)
1. การเรียงลำดับภายใน(Internal Sorting) เป็นการเรียงลำดับข้อมูลภายในหน่วยความจำหลัก (Primary Memory) ซึ่งจะเหมาะสมกับข้อมูลทีมีปริมณไม่มาก เนื่องจากหน่วยความจำหลักมีขนาดจำกัด ซึ่งมีวิธีการเรียงลำดับข้อมูล โดยสมารถแบ่งประเภทย่อยได้ดังนี้
1.1 วิธีเรียงลำดับแบบแทรก (Insertion )
1.2 วิธีเรียงลำดับแบบเลือก (Selection)
2. การเรียงลำดับภายนอก (External Sorting) เป็นการเรียงลำดับข้อมูลด้วยการใช้หน่วยความจำเฉพาะส่วนข้อมูลที่ต้องการจัดเรียง เหมาะสมกับการใช้กับข้อมูลทีมีปริมาณมาก เนื่องจากจะไม่สามารถนำไปใส่ไว้ในหน่วยความจำหลักเพื่อประมวลผลพร้อมกันได้ ซึ่งมีวิธีการเรียงลำดับข้อมูล ได้แก่
YouTube Video
YouTube Video
YouTube Video
YouTube Video
YouTube Video
YouTube Video
Sequential Search Vs Binary Search
Sequential Search คืออะไร
Sequential Search หรือ Linear Search คือ การหาข้อมูลแบบเป็นลำดับขั้นตอน โดยจะค้นหาตั้งแต่ตัวแรกเรียงลำดับไปทีละตัวจนกว่าจะพบข้อมูลที่ต้องการ หรือเปรียบเทียบไปจนถึงตัวสุดท้าย การค้นหาวิธีนี้เป็นวิธีที่ง่ายที่สุด อัลกอริทึ่มในการค้นหาไม่ซับซ้อนสามารถใช้กับข้อมูลที่เรียงลำดับแล้วหรือข้อมูลที่ยังไม่ได้เรียงลำดับก็ได้ โดยผลลัพธ์จากการค้นหาข้อมูลจะมีความเป็นไปได้อยู่ 2 แบบ คือ
1.พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์(Successful Search)
ตัวอย่างการค้นหา
2. ไม่พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์ (Unsuccessful Search)
Binary Search คืออะไร
เทคนิคการค้นหาข้อมูลด้วยวิธีนี้
1. กำหนดข้อมูลที่ต้องการค้นหาและทำการเรียงข้อมูลตามความต้องการ เรียงจากมากไปน้อย หรือจากน้อยไปมากก็ได้
2. ทำการแบ่งข้อมูลออกเป็น 2 ส่วน แล้วทำการหาค่ากลาง
3. เมื่อทราบแล้วว่าค่าของคีย์ฟิลด์อยู่ครึ่งแรกหรือครึ่งหลังแล้ว ก็จะนำข้อมูลในครึ่งดังกล่าวทำการหาค่ากลางอีก ทำแบบนี้ไปเรื่อย ๆ จนกระทั้งได้ข้อมูลที่ต้องการ หรือจนกระทั่งไม่สามารถแบ่งข้อมูลได้อีก
เปรียบเทียบระหว่าง Sequential Search และ Binary Search
log(n) = Binary Search
แหล่งเรียนรู้ Sorting
https://visualgo.net/en/sorting
https://www.toptal.com/developers/sorting-algorithms
Teacher Nu