DTS 10-09/09/52

กราฟ และ sorting
กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น
(Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูล
ทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษ แบบหนี่งขอ'กราฟโดย
ทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ
เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด กราฟมีลักษณะ
เป็นเซ็ตของ จุด (Point) และเซ็ตของเส้น (Line) ซึ่งแต่ละเส้นทำหน้า
ที่เชื่อมต่อจุดเข้าด้วยกัน แต่ละจุดเรียกว่าโหนด (Node) ของกราฟ
และเส้นเรียกว่าเอจ (Edge) บางครั้งเอจจะ เรียกว่าอาร์ค (Arc) และ
โหนดเรียกว่าเวอร์ทิค (Vertice) โดยกำหนดให้กราฟ G มีเซ็ต
ของโหนดเป็น VG และเซ็ตของเอจเป็น EG

การวิ่งตามเส้นทางในกราฟ
แอปพลิเคชั่นที่เขียนขึ้นมาเมื่อใช้งานกราฟส่วนใหญ่ต้องเข้าไปเรียกใช้
งานในแต่ละ โหนด เช่น การพิมพ์รายการกิจกรรมในระบบการบริหารจัด
การโครงการ การแสดงผล ระยะทางระหว่างเมือง เทคนิคพื้นฐานการวิ่ง
ตามเส้นทางในกราฟ (Graph Traversal) ที่จะกล่าวถึง คือ การวิ่งตาม
แนวกว้างก่อน (Breadth – first) และการวิ่งตามแนวลึกก่อน (Depth – first)
การวิ่งตามเส้นทางมีสิ่งที่ต้องระวัง คือ การวิ่งไปถึงแต่ละโหนดควรมี
เพียงครั้งเดียว การวิ่งซ้ำโหนดเดิมทำให้การทำงานและผลที่ได้เกิดขึ้นซ้ำ
จากการวิ่งย้อน ตามเส้นทางที่เคยผ่านมาแล้ว และมีหลายเส้นทางที่เชื่อม
ต่อระหว่างสองโหนด การเขียน อัลกอริทึมการวิ่งตามเส้นทางในกราฟจะใช้
เครื่องหมายหรือตัวมาร์ก (Mark) บอกให้ทราบว่า มีการวิ่งมายังโหนดนี้แล้ว
โดยก่อนหน้านี้จะถูกมาร์กว่ายังไม่วิ่งมา หรือเปลี่ยนมาใช้ตัวมาร์ก กับเอจ
แทน ดังนั้น เอจที่ผ่านไปแล้วจะไม่ถูกรวมกับเอจอื่น ๆ ที่เหลือ เครื่องหมาย
หรือตัวมาร์ก จะใช้เป็นมาร์กบิต (Mark Bit) เก็บไว้ในแต่ละโหนดหรือเอจ

การวิ่งตามแนวกว้างก่อน
การวิ่งตามเส้นทางในกราฟตามแนวกว้างก่อน (Breath – first Traversal)
หรือการค้นหา ตามแนวกว้างก่อน (Breath – first Traversal) เริ่มด้วยการ
เลือก มาหนึ่งโหนดเป็นตำแหน่ง เริ่มต้นและทำเครื่องหมายว่าวิ่งผ่านมา
แล้ว จากนั้นวิ่งไปยังโหนดทุกโหนดที่ติดกับโหนด นี้และยังไม่วิ่งผ่าน
และทำ เครื่องหมาย ทำเช่นนี้จะกระทั่งวิ่งผ่านทุก ๆ โหนดที่มีอยู่ในกราฟ
การวิ่งตาม แนวกว้างในกราฟจากรูปที่ 10.13 ผลจากการวิ่งไปยังแต่ละ
โหนดจะมีลำดับเป็น 1,2,3,4,5,6,7,8 หรือมีลำดับเป็น 1,3,2,6,5,4,7,8 ก็ได้
ขึ้นอยู่กับการเลือกโหนดที่ จะวิ่งผ่าน ทางด้านซ้ายหรือขวาก่อน
อัลกอริทึมการวิ่งตามเส้นทางในแนวกว้าง ก่อนจะใช้โครงสร้าง
ข้อมูลคิวเพื่อเก็บโหนดที่วิ่งผ่านไปแล้วในแต่ละระดับของ กราฟ แต่ละ
โหนดที่เก็บในคิวจะใช้ สำหรับวิ่งไปยังโหนดติดกันที่ยังไม่ได้วิ่งไป
ทำจนวิ่งผ่านทุกโหนดในกราฟและสิ้นสุดลงเมื่อ คิวว่าง อัลกอริทึมการ
วิ่งตาม เส้นทางในแนวกว้างก่อน

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

(1) การเรียงลำดับแบบภายใน (internal sorting)
เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก
เวลาที่ใช้ ในการเรียงลำดับจะคำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและ
เลื่อนข้อมูลภายใน ความจำหลัก

(2) การเรียงลำดับแบบภายนอก(external sorting)
เป็นการเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการ
เรียงลำดับ ข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ในการเรียงลำดับต้อง
คำนึงถึงเวลาที่เสียไป ระหว่างการถ่ายเทข้อมูลจากหน่วยความจำหลัก
และหน่วยความจำสำรองนอกเหนือ จากเวลาที่ใช้ในการเรียงลำดับข้อมูล
แบบภายในการเรียงลำดับแบบเลือก (selection sort) ทำการเลือกข้อมูลมา
เก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ทีละตัว โดยทำการค้นหา ข้อมูลนั้น
ในแต่ละรอบแบบเรียงลำดับการเรียงลำดับแบบเลือกเป็นวิธีที่ง่าย แต่เสีย
เวลาในการจัดเรียงนาน โดยจะทำการเลือกข้อมูลมาเก็บไว้ตามตำแหน่ง
ที่กำหนด คือ กำหนดให้เรียงข้อมูลจากค่าน้อยไปหาค่ามาก ก็จะทำการ
เลือกข้อมูลตัวที่มีค่าน้อยที่สุดมา อยู่ที่ตำแหน่งแรกสุด และค่าที่อยู่
ตำแหน่งแรกก็จะมาอยู่แทนที่ค่าน้อยสุด แล้วทำการ เลือกไปเรื่อยๆ
จนครบทุกค่า ค่าที่ได้ก็จะเรียงจากน้อยไปหามาก

การเรียงลำดับแบบฟอง (Bubble Sort)
เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลในตำแหน่งที่อยู่ติดกัน
1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน
2. ถ้าเป็นการเรียงลำดับจากน้อยไปมากให้นำข้อมูลตัวที่มีค่าน้อยกว่า
อยู่ในตำแหน่งก่อน ข้อมูลที่มีค่ามาก ถ้าเป็นการเรียงลำดับจากมากไป
น้อยให้นำข้อมูล ตัวที่มีค่ามากกว่าอยู่ ในตำแหน่งก่อนข้อมูลที่มีค่าน้อย

การเรียงลำดับแบบแทรก (insertion sort)
เป็นวิธีการเรียงลำดับที่ทำการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มี
สมาชิกทุกตัวเรียง ลำดับอยู่แล้ว และทำให้เซตใหม่ที่ได้นี้มีสมาชิกทุกตัว
เรียงลำดับด้วย วิธีการเรียงลำดับจะ

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

2. จะต้องจัดให้ข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก
และถ้าเรียงจาก มากไปน้อยก็จะจัดให้ข้อมูลที่มีค่ามากอยู่ในตำแหน่งก่อน
การเรียงลำดับแบบฐานเป็นวิธีที่ พิจารณาเลขที่ละหลัก โดยจะพิจารณาเลข
หลักหน่วยก่อน แล้วทำการจัดเรียงข้อมูลทีละตัวตามกลุ่มหมายเลข
จากนั้นนำข้อมูลที่จัดเรียงในหลัก หน่วยมาจัดเรียงในหลักสิยต่อไปเรื่อยๆ
จนครบทุกหลัก ก็จะได้ข้อมูลที่ต้องการ การเรียง ลำดับแบบฐานไม่ซับซ้อน
แต่ใช้เนื้อที่ในหน่วยความจำมาก