สรุป กราฟ (Graph) ต่อ
การท่องไปในกราฟ (Graph traversal) คือ การเข้าไปเยือนโหนดในกราฟ หลักการทำงาน คือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว
เทคนิคการท่องไปในกราฟมี 2 แบบ
1.การท่องแบบกว้าง (Breadth First Traversal) โดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นที่ละระดับ จนเยือนหมดทุกโหนดในกราฟ (แบบคิว)
2.การท่องแบบลึก (Depth First Traversal) คล้ายกับการท่องทีละระดับของทรี กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีจนไปสู่ปลายวิถี จากนั้นย้อนกลับ (backtrack) ตามแนววิถีเดิม จนสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่นๆ เพื่อเยือนโหนดอื่นๆ ต่อไปจนครบทุกโหนด (แบบสแตก)
สรุป Sorting
การเรียงลำดับ (sorting) เป็นการจัดให้เป็นระเบียบ มีแบบแผน ช่วยให้การค้นหาสิ่งของหรือข้อมูล สามารถทำได้รวดเร็วและมีประสิทธิภาพ
การเรียงลำดับอย่างมีประสิทธิภาพ
หลักเกณฑ์ในการพิจารณาเพื่อเลือกวิธีการเรียงลำดับที่ดีและเหมาะสมกับระบบงาน
1.เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม
2.เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตามโปรแกรมที่เขียน
3.จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่วิธีการเรียงลำดับ มีหลายวิธีที่สามารถใช้ในการเรียงลำดับข้อมูลได้
วิธีการเรียงลำดับแบ่งออกเป็น 2 ประเภท
1.การเรียงลำดับภายใน (internal sorting) เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก
2.การเรียงลำดับแบบภายนอก (external sorting) เป็นการเรียนลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง เป็นการเรียงลำดับข้อมูลในแฟ้มข้อมูล (file)
การเรียงลำดับแบบเลือก (selection sort)
ข้อมูลจะอยู่ทีละตัว โดยทำการค้นหาข้อมูลในแต่ละรอบแบบเรียงลำดับ ถ้าเป็นการเรียงลำดับจากน้อยไปมาก
1.ในรอบแรกจะทำการค้นหาข้อมูลตัวที่มีค่าน้อยที่สุดมาเก็บไว้ที่ตำแหน่งที่ 1
2.ในรอบที่สองนำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บไว้ที่ตำแหน่งที่สอง
3.ทำแบบนี้ไปเรื่อยๆ จนครบทุกค่า ในที่สุดจะได้ข้อมูลเรียงลำดับจากน้อยไปมากตามที่ต้องการการจัดเรียงลำดับแบบเลือกเป็นวิธีที่ง่ายและตรงไปตรงมา แต่มีข้อเสียตรงที่ใช้เวลาในการจัดเรียงนาน เพราะแต่ละรอบต้องเปรียบเอียบกับข้อมูลทุกตัว
การเรียงลำดับแบบฟอง (Bubble Sort)
เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลในตำแหน่งที่อยู่ติดกัน
1.ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน
2.ถ้าเป็นการเรียงลำดับจากน้อยไปมากให้นำข้อมูลตัวที่มีค่าน้อยกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก ถ้าเป็นการเรียงลำดับจากมากไปน้อยให้นำข้อมูล ตัวที่มีค่ามากกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่าน้อยการจัดเรียงลำดับแบบฟองเป็นวิธีที่ไม่ซับซ้อนมาก เป็นวิธีการเรียงลำดับที่นิยมใช้กันมากเพราะมีรูปแบบที่เข้าใจง่าย
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น