DTS 10-09/09/52

การเรียงลำดับ Sorting และ การค้นหาข้อมูล (Searching)

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

การเรียงลำดับแบบเลือก (Selection sort)

- ถ้าเป็นการเรียงลำดับจากน้อยไปหามาก
1.รอบแรกจะทำการค้นหาข้อมูลตัวที่มีค่าน้อยที่สุดมาเก็บไว้ที่ตำแหน่งที่ 1
2.รอบที่สองนำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บที่ตำแหน่งที่2
3.ทำเช่นนี้ไปเรื่อยๆ จนกระทั่งครบทุกค่า ที่สุดจะได้ข้อมูลเรียงจากน้อยไปหามากตามที่ต้องการ


การเรียงลำดับแบบฟอง (Bubble sort)

-วิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลในตำแหน่งที่อยู่ติดกัน
1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน

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



การเรียงลำดับแบบเร็ว (quick sort)
เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็ว วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูล ขึ้นมาหนึ่งค่าเป็นหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่านี้ เมื่อได้ตำแหน่งที่ถูกต้องแล้ว ใช้ค่าหลักนี้เป็นหลัก ในการแบ่งข้อมูลออกเป็นสองส่วน
ถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่ในตอนหน้าข้อมูล ทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่งส่วน
การจัดเรียงลำดับแบบเร็วเป็นวิธีที่ค่อนข้างซับซ้อน แต่มีประสิทธิภาพค่อนข้างสูง
คือค่าหลักที่เลือกแบ่งแล้วข้อมูลอยู่ ตรงกลางกลุ่มพอดี การเปรียบเทียบเป็นดังนี้
จำนวนครั้งการเปรียบเทียบ = n log2 n ครั้ง
การเรียงลำดับแบบแทรก (insertion sort)
เป็นการเรียงลำดับที่ทำการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มีสมาชิกทุกตัวเรียงลำดับอยู่แล้ว ทำให้เซตใหม่ที่ได้นี้มีสมาชิกทุกตัวเรียงลำดับด้วย
1. เริ่มต้นเปรียบเทียบจากข้อมูลในตำแหน่งที่ 1 กับ 2 หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้ายก็ได้
2. จะต้องจัดให้ข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งก่อน ข้อมูลที่มีค่ามาก ถ้าเรียงจากมากไปน้อยก็จะจัดให้ข้อมูลที่มีค่ามากอยู่ในตำแหน่งก่อน
การเรียงลำดับแบบฐาน (radix sort)
โดยการพิจารณาข้อมูลทีละหลัก
1.เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุด คือ ข้อมูลเป็นเลขจำนวนเต็ม พิจารณาหลักหน่วยก่อน
2.การเรียงจะนำข้อมูลเข้ามาที่ละตัว นำไปเก็บไว้ที่จัดสำหรับค่านั้น เป็นกลุ่มๆ ตามลำดับการเข้ามา
3.ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน เรียงกลุ่มที่มีค่าน้อยที่สุดก่อนแล้วเรียงไปเรื่อยๆจนหมดทุกกลุ่ม
4.ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลัก หน่วยเรียบร้อยแล้ว มาพิจารณาจัดเรียงในหลักสิบต่อไป ทำไปเรื่อยๆจนครบทุกหลัก จะได้ข้อมูลที่เรียงจากน้อยไปมาก



การค้นหาข้อมูล (Searching)
คือ การใช้วิธีการค้นหากับโครงสร้างข้อมูล ดูว่าข้อมูลตัวที่ต้องการถูกเก็บอยู่ในโครงสร้างแล้วหรือยัง
วัตถุประสงค์
1. เพื่อดูรายละเอียดเฉพาะข้อมูลที่ต้องการ ดึงข้อมูลที่ค้นหาออกจากโครงสร้าง
2. เปลี่ยนแปลงแก้ไขรายละเอียดบางอย่าง หรือ เพิ่มข้อมูลตัวที่ค้นหา ถ้าพบว่าไม่เคยเก็บไว้ในโครงสร้างเลย ไปเก็บไว้ในโครงสร้าง เพื่อใช้งานต่อไป
การค้นหาข้อมูล (Searching)
แบ่งเป็น 2 ประเภท
-การค้นหาข้อมูลแบบภายใน(Internal Searching)
-การค้นหาข้อมูลแบบภายนอก(External Searching)
1.การค้นหาแบบเชิงเส้น หรือ การค้นหาตามลำดับ (Linear)
คือ ให้นำข้อมูลที่หามาเปรียบเทียบกับข้อมูลตัวแรกในแถวลำดับ
ถ้าไม่เท่ากันให้เปรียบเทียบกับข้อมูลตัวถัดไป
ถ้าเท่ากันให้หยุดการค้นหาหรือการค้นหาจะหยุดเมื่อพบข้อมูลที่ต้องการ หรือหาข้อมูลทุกจำนวนในแถวลำดับแล้วไม่พบ
2.การค้นหาแบบเซนทินัล(Sentinel)
คือ- เพิ่มขนาดของแถวลำดับ ที่ใช้เก็บข้อมูลอีก1ที่
-นำข้อมูลที่จะใช้ค้นหาข้อมูลใน array ไปฝากที่ต้นหรือ ท้าย array
-ตรวจสอบผลลัพธ์จาการหา
โดยตรวจจากตำแหน่งที่พบ ถ้าตำแหน่งที่พบมีค่าเท่ากับn-1 แสดงว่า หาไม่พบ นอกนั้นถือว่าพบข้อมูล
3.การค้นหาแบบไบนารี (Binary Search)
คือ ข้อมูลถูกแบ่งออกเป็นสองส่วน แล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา
หาตัวแทนข้อมูลเพื่อนำมาเปรียบเทียบกับค่าที่ต้องการ
จากสูตร mid= (low+high)/ 2
Mid=ตำแหน่งกลาง
Low=ตำแหน่งต้นแถวลำดับ
high= ตำแหน่งท้ายของแถวลำดัว