Sorting และSearching
Sorting การเรียงลำดับแบบเร็ว
การเรียงลำดับแบบเร็ว (quick sort) เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็วในการทำงาน วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูลขึ้นมาหนึ่งค่าเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูกต้องแล้วใช้ค่าหลักนี้เป็นหลักในการแบ่งข้อมูลออกเป็น สองส่วน ถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่ในตอนหน้าข้อมูลทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่งส่วน และอีกส่วนหนึ่งจะอยู่ในตำแหน่งตอนหลังข้อมูลทั้งหมดจะมีค่ามากกว่าค่าหลัก แล้วนำแต่ละส่วนย่อยไปแบ่งย่อยในลักษณะเดียวกันต่อไป จนกระทั่งแต่ละส่วนไม่สามารถแบ่งย่อยได้อีกต่อไปจะได้ข้อมูลที่มีการเรียงลำดับตามที่ต้องการ
กรณีที่แย่ที่สุด คือ กรณีที่ข้อมูลมีการเรียงลำดับอยู่แล้ว อาจจะเรียงจากน้อยไปหามากหรือจากมากไปน้อยที่สุดหรือมากที่สุด จำนวนครั้งของการเปรียบเทียบจะมากที่สุดดังนี้
กรณีที่ดีที่สุด คือ กรณีที่ค่าหลักที่เลือกแบ่งข้อมูลอยู่ตรงกลางกลุ่มพอดี และในแต่ละส่วนย่อยก็เช่นเดียวกันจำนวนครั้งของการเปรียบเทียบเป็นดังนี้
จำนวนครั้งของการเปรียบเทียบ = n log2n คร้ง
Searching การค้นหาข้อมูล
การค้นหา แบ่งออกเป็น 2ประเภท ตามแหล่งที่จัดเก็บข้อมูลเช่นเดียวกับการเรียงลำดับ
1. การค้นหาข้อมูลแบบภายใน
2. การค้นหาข้อมูลแบบภายนอก
การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ (Linear)
เป็นวิธีที่ใช้กับข้อมูลที่ยังไม่ได้เรียงลำดับ
หลักการคือ ให้นำข้อมุลที่จะหามาเปรียบเทียบกับข้อมูลตัวแรกในแถวลำดับ
1. ถ้าไม่เท่ากันให้เปรียบเทียบกับข้อมูลตัวถัดไป
2. ถ้าเท่ากันให้หยุดการค้นหา หรือการค้นหาจะหยุดเมื่อพบข้อมูลที่ต้องการหรือหาข้อมูลทุกจำนวนในแถวลำดับแล้วไม่พบ
การค้นหาแบบเซนทินัล (sentinel)
เป็นวิธีการค้นหาแบบเดียวกับวิธีการค้นหาแบบเชิงเส้นแต่ประสิทธิภาพดีกว่าตรงที่เปรียบเทียบน้อยครั้งกว่า พัฒนามาจากอัลกอริทึ่มแบบเชิงเส้น
หลักการ
1.เพิ่มขนาดของแถวลำดับ ที่ใช้เก็บข้อมูลอีกหนึ่งที่
2. นำข้อมูลที่จะใช้ค้นหาข้อมูลใน array ไปฝากที่ต้นหรือ ท้าย array
3. ตรวจสอบผลลัพธ์จากการหา
การค้นหาแบบไบนารี (Binary Search)
การค้นหาแบบไบนารีทรีใช้กับข้อมูลที่ ถูกจัดเรียงแล้วเท่านั้น
1. หาตัวแทนข้อมูลเพื่อนำมาเปรียบเทียบกับค้าที่ต้องการค้นหาตำแหน่งตัวแทนข้อมูลหาได้ขากสูตร
mid =(low+hing)/2
mid คือ ตำแหน่งกลาง,low คือ ตำแหน่งต้นแถวลำดับ
hing คือ ตำแหน่งท้ายของข้อมูล
2. การค้นหาแบบไบนารี (Binary Search)
การค้นหาแบบไบนารีใช้กับข้อมูลที่ถูกจัดเรียงแล้วเท่านั้น หลักการของการค้นหาคือ ข้อมูลถูกแบ่งออกเป็นสองส่วน แล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา ถ้าข้อมูลมีการเรียงจากน้อยไปหามาก เมื่อเปรียบเทียบแล้วคีย์มีค่ามากกว่าค่ากลาง แสดงว่าต้องทำการค้นหาข้อมูลในครึ่งหลังต่อไป จากนั้นนำข้อมูลครึ่งหลังมาหาค่ากลางต่อ ทำอย่างนี้ไปเรื่อย ๆ จนกว่าจะได้ข้อมูลที่ต้องการ เช่นต้องการหาว่า 12 อยู่ในลิสต์ (1 4 6 8 10 12 18 19) หรือไม่ เริ่มการค้นหาแบบไบนารีด้วยการเปรียบเทียบกับค่ากลางในลิสต์ คือค่า a[4] ซึ่งเก็บค่า 8 ซึ่ง 12 > a[4] หมายความว่าค่า 12 ควรจะอยู่ในข้อมูลด้านขวาของ a[4] คือ ช่วง a[5] …a[8] โดยไม่สนใจช่วงข้อมูล a[1] …a[3] และใช้วิธีการค้นหาแบบไบนารีเช่นเดิมอีกกับชุดข้อมูลครึ่งหลัง คือ a[5] …a[8] นั่นคือ เปรียบเทียบกับค่ากลางของชุดข้อมูลครึ่งหลัง (a[5] …a[8] ) คือค่า a[6] ซึ่งเก็บค่า 12 ซึ่ง 12 = a[6]
จะได้ว่าค่า 12 อยู่ในตำแหน่งที่ 6 ในลิสต์
ไม่มีความคิดเห็น:
แสดงความคิดเห็น