บทที่ 6

ทรี (TREE)

ทรี (Tree)ป็นโครงสร้างข้อมูลที่ความสัมพันธ์ ระหว่าง โหนดจะมัความสัมพันธ์ลดหลั่นกันเป็นลำดับ เช่น (Hierarchical Relationship) ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงาน ต่าง ๆ อย่างแพร่หลาย สวนมากจะใชสำหรับแสดง ความสัมพันธ์ระหว่างข้อมูล เช่น แผนผังองค์ประกอบของหน่วยงานต่าง ๆ โครงสร้างสารบัญหนังสือ เป็นต้นแต่ละโหนดจะมีความสัมพันธ์กับ โหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆโหนด เรียกโหนดดั้งกล่าวว่า โหนดแม่(Parent orMother Node)โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก (Child or Son Node)โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหดราก (Root Node) Data Structure โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน รียกว่า โหนดพี่น้อง (Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (Leave Node)เส้นเชื่อมแสดงความสัมพันธ์ระหว่าง โหนดสองโหนดเรียกว่า กิ่ง (Branch)

นิยามของทรี

1. นิยามทรีด้วยนิยามของกราฟ ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop)ในโครงสร้าง โหนดสองโหนด ใดๆในทรีต้องมีทางตัดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่ง ทั้งหมด N-1 เส้น การเขียนรูปแบบทรี อาจเขียนได้ 4

2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่า นัลทรี (Null Tree)และถามโหนดหนึ่งเป็นโหดราก ส่วนที่เหลือจะแบ่งเป็น ทรีย่อย (Sub Tree)T1, T2, T3,…,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี

นิยามที่เกี่ยวข้องกับทรี

1.ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออกหรือเซตของทรีทแยกจากกัน (Disjoint Trees)

2.ทรีที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมี ความสัมพันธ์ที่แน่นอน เช่น ไปทางขวาไปทางซ้าย เป็นต้น

3.ทรีคล้าย (Similar Tree) คือทรีที่มีโครงสร้างเหมือนกันหรือทรีที่มีรูปร่างของทรีเหมือนกันโดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด

4.ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน

5.กำลัง (Degree) หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ เช่น

ในรูปโหนด “B” มีกำลังเป็น 1 เพราะมีทรีย่อย คือ {“D”}ส่วนโหนด “C” มีค่ากำลังเป็นสองเพราะมีทรีย่อย คือ {“E”, “G”, “H”, “I”} และ {“F”}

6.ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่ระดับ 1 และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1หน่วยซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่างจากโหนดราก เรียกวา ความสูง (Height)หรือความ ลึก (Depth)

การแทนที่ทรีในหน่วยความจำหลัก

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

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

การแทนทรีด้วยโหนดขนาดเท่ากันค่อนข้างใช้เนื้อที่จำนวนมากเนื่องจากแต่ละโหนดมี จำนวนโหนดลูกไม่เท่ากันหรือบางโหนดไม่มี โหนดลูกเลยถ้าเป็นทรีที่แต่ละโหนดมีจำนวนโหนดลูกที่แตกต่างกันมากจะเป็นการสิ้นเปลือง เนื้อที่ในหน่วยความจำโดยเปล่าประโยชน์

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

โครงสร้างทรีที่แต่ละโหนดมีลิงค์ฟิลด์แค่สองลิงค์ฟิลด์ ซึ่งช่วยให้ประหยัดเนื้อที่ในการจัดเก็บได้มาก เรียกโครงสร้างทรีที่แต่ละโหนดมีจำนวนโหนดลูกไม่เกินสองหรือแต่ละโหนดมีจำนวน ทรีย่อยไม่เกินสองนี้ว่า ไบนารีทรี (Binary Tree)

ไบนารีทรีที่ทุก ๆ โหนดมีทรีย่อยทางซ้ายและทรีย่อยทางขวา ยกเว้นโหนดใบ และโหนดใบทุกโหนดจะต้องอยู่ที่ระดับเดียวกันเรียกว่า ไบนารีทรีแบบสมบูรณ์ (complete binary tree)สามารถคำนวณจำนวนโหนดทั้งหมดในไบนารีทรีแบบสมบูรณ์ได้ถ้ากำหนดให้ Lคือระดับของโหนดใด ๆ และ N คือจำนวนโหนดทั้งหมดในทรีจะได้ว่า
ระดับ 1 มีจำนวนโหนด 1 โหนด
ระดับ 2 มีจำนวนโหนด 3 โหนด
ระดับ 3 มีจำนวนโหนด 7 โหนด
ระดับ L มีจำนวนโหนด 2L - 1โหนด
นั้นคือ จำนวนโหนดทั้งหมดในทรีสมบูรณ์ที่ มี L ระดับ สามารถคำนวณได้จากสูตรดั้งนี้

การแปลงทรีทั่วไปให้เป็นไบนารีทรี

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

การท่องไปในไบนารีทรี

ปฏิบัติการที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี (Traversing Binary Tree) เพื่อเข้าไปเยือนทุก ๆโหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆโหนด ๆ ละหนึ่งครั้งวิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการเยือนอย่างไร โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)ทรีย่อยทางซ้าย (แทนด้วย L)หรือทรีย่อยทางขวา (แทนด้วย R)

มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นคือ NLR LNR และ LRN ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้
1. การท่องไปแบบพรีออร์เดอร์(Preorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธีNLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์

2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LNRมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์

3. การท่องไปแบบโพสออร์เดอร์(Postorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์

เอ็กซ์เพรสชันทรี (Expression Tree)

เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ(Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรืออาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression)นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอนในการคำนวณตามความสำคัญของเครื่องหมายด้วยโดยมีความสำคัญตามลำดับดังนี้

- ฟังก์ชัน
- วงเล็บ
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน (unary)
- คูณ หรือ หาร
- บวก หรือ ลบ
- ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
การแทนนิพจน์ในเอ็กซ์เพรสชันทรี ตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบส่วนตัวดำเนินการจะเก็บในโหนดกิ่งหรือโหนดที่ไม่ใช่โหนดใบเช่น นิพจน์ A + B สามารถแทนในเอ็กซ์เพรสชันทรีได้ดังนี้

ไบนารีเซิร์ชทรี

ไบนารีเซิร์ชทรี (Binary Search Tree)เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน

ปฏิบัติการในไบนารีเซิร์ชทรี ปฏิบัติการเพิ่มโหนดเข้าหรือดึงโหนดออกจากไบนารีเซิร์ชทรีค่อนข้างยุ่งยากกว่าปฏิบัติการในโครงสร้างอื่น ๆเนื่องจากหลังปฏิบัติการเสร็จเรียบร้อยแล้วต้องคำนึงถึงความเป็นไบนารีเซิร์ชทรีของทรีนั้นด้วยซึ่งมีปฏิบัติการดังต่อไปนี้

(1) การเพิ่มโหนดในไบนารีเซิร์ชทรี การเพิ่มโหนดใหม่เข้าไปในไบนารีเซิร์ชทรี ถ้าทรีว่างโหนดที่เพิ่มเข้าไปก็จะเป็นโหนดรากของทรี ถ้าทรีไม่ว่างต้องทำการตรวจสอบว่าโหนดใหม่ที่เพิ่มเข้ามานั้นมีค่ามากกว่าหรือน้อยกว่าค่าที่โหนดราก ถ้ามีค่ามากกว่าหรือเท่ากันจะนำโหนดใหม่ไปเพิ่มในทรีย่อยทางขวาและถ้ามีค่าน้อยกว่านำโหนดใหม่ไปเพิ่มในทรีย่อยทางซ้ายในทรีย่อยนั้นต้องทำการเปรียบเทียบในลักษณะเดียวกันจนกระทั่งหาตำแหน่งที่สามารถเพิ่มโหนดได้ ซึ่งโหนดใหม่ที่

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

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

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

ค. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้ายและทรีย่อยทางขวาต้องเลือกโหนดมาแทนโหนดที่ถูกดึงออก โดยอาจจะเลือกมาจากทรีย่อยทางซ้ายหรือทรีย่อยทางขวาก็ได้
- ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรีย่อยทางซ้ายต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อยทางซ้ายนั้น
- ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมาจากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อยทางขวานั้น

บทที่ 7

กราฟ (Graph)

กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด

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

กราฟสามารถเขียนแทนด้วยสัญลักษณ์ ดังนี้

G = ( V , E )

G คือ กราฟ

V คือ กลุ่มของ vertex

E คือ กลุ่มของ edge

ศัพท์ที่เกี่ยวข้อง

1.เวอร์เทก (Vertex) หมายถึง โหนด

2.เอดจ (Edge) หมายถึง เส้นเชื่อมของโหนด

3.ดีกรี (Degree) หมายถึง จำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด

4.แอดจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเชื่อมโยงกัน

ตัวอย่างของกราฟในชีวิตประจำวัน เช่น กราฟของการเดินทางระหว่างเมือง ซึ่ง vertex คือ กลุ่มของเมืองต่างๆ และ edge คือ เส้นทางเดินระหว่างเมือง หรือ ในเครือข่ายคอมพิวเตอร์ (Computer Network) vertex ก็คือ กลุ่มของเครื่องคอมพิวเตอร์ หรือโหนดต่างๆ และ edge ก็คือ เส้นทางการติดต่อสื่อสารระหว่างโหนดต่างๆ เป็นต้น

ประเภทของกราฟ

แบ่งเป็น 3 ประเภทโดยแบ่งตามประเภทของ edge ได้ดังนี้

1. Direct Graph (กราฟแสดงทิศทาง) เป็นกราฟที่แสดงเส้นเชื่อมระหว่าง vertex โดแสดงทิศทางของการเชื่อมต่อด้วย

2. Undirected Graph กราฟที่แสดงเส้นเชื่อมต่อระหว่าง vertex แต่ไม่แสดงทิศทางของการเชื่อมต่อ

3. Cyclic Graph กราฟที่มีเส้นเชื่อมต่อระหว่าง vertex ที่ทำให้ vertex มีลักษณะเป็นวงจรปิด (Cycle) เส้นเชื่อมต่อระหว่าง vertex อาจจะแสดงทิศทางหรือไม่แสดงทิศทางการเชื่อมต่อก็ได้

เส้นทาง (Path)

เส้นทางคือการเดินทางจาก vertex หนึ่งไปยังอีก vertex หนึ่งที่ต้องการ โดยผ่าน edge ที่เชื่อมระหว่าง vertex

ความยาวของเส้นทาง (The length of path) คือ จำนวนของ edge ในเส้นทางเดินนั้น ว่ามีจำนวนเท่าไหร่ ในการเดินทางจาก vertex หนึ่ง ไปยังอีก vertex หนึ่ง ถ้าหากเส้นทางประกอบด้วย vertex จำนวน N ความยาวของเส้นทางจะเท่ากับ N-1

ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้

การแทนที่กราฟด้วยเมตริกซ์

โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้ โดยกราฟที่ประกอบด้วย vertex จำนวน N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N x N โดยค่าในเมตริกซ์จะประกอบด้วย ค่า 0 และ 1

ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง และ

ค่า 1 จะใช้แทนมี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง

ตัวอย่างจากรูปกราฟแบบ Direct Graph

สามารถแทนที่กราฟด้วยเมตริกซ์ดังนี้

ตัวอย่าง หากเป็นกราฟแบบ Undirected Graph

การคำนวณเส้นทางระหว่าง vertex โดยใช้ Adjacency Matrix

จากการแทนที่กราฟด้วยเมตริกซ์ เราสามารถนำเมตริกซ์ที่ได้มาคำนวณหาจำนวนเส้นทางระหว่าง vertex ต้นทางและปลายทางที่มีจำนวน edge ต่างๆ ได้

ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 3 เส้นได้ดังนี้

ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 4 เส้นได้ดังนี้

การท่องไปในกราฟ (Graph Traversal)

การท่องไปในกราฟ (Graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยใช้หลักการเดียว กับ

การเดินทางเข้าไปในทรี (Tree Traversal) คือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรี

เพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง เนื่องจากรูปแบบ

การเชื่อมต่อระหว่างโหนดของกราฟไม่เหมือนกับทรี สำหรับเทคนิคการท่องไปในกราฟมี 2 แบบ ดังนี้

วิธี Depth First Traversal

การท่องแบบลึก (Depth First Traversal) การทำงานคล้ายกับการท่องทีละระดับของทรี โดย

กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อน

กลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนด

อื่น ๆ ต่อไปจนครบทุกโหนด

1. กรรมวิธีท่องไปในกราฟจากจุดหนึ่งไปยังอีกจุดหนึ่งนั้นอาจทำได้หลายวิธี แต่วิธีที่นิยมใช้และง่ายก็คือการ

ท่องไปในกราฟโดยอาศัยการท่องไปบน adjacency matrix

1. สมมติว่า adjacency matrix คือดังรูป และเราจะเดินทางจาก C ไป E

1. เริ่มต้นที่แถวประจำโหนด(visit C) จากนั้นหาสมาชิกที่มีความสัมพันธ์ ซึ่งจะได้ C->A (visit A)

2. ที่แถว A ไล่ต่อไปได้ C->A->B (visit B)

3. ที่แถว B ไล่ข้าม A ที่เคย visit ข้าม C แสดงว่า แนว C->A->B ใช้ไม่ได้ (ตัน)

4. ย้อนกลับ C-A-> ข้ามB(ตัน) ข้าม C (visit แล้ว) ไปต่อ D C->A->D

5. ที่แถว D ไล่ข้าม A/C (visit แล้วทั้งคู่) ไป E ถึงปลายทาง

6. ได้ C->A->D->E เป็นคำตอบแรก

7. เราทำซ้ำต่อไปได้โดยข้ามเส้นที่เคยตัน/visit แล้ว

เราสามารถเขียนคำสั่งการทำงานออกมาได้ในลักษณะของการเรียกตนเอง และมีการอาศัย flag กำหนดบ่งบอกว่าจุดใดได้ visit ไปแล้ว (ไม่ว่าจะค้นพบหรือไม่พบเส้นทางก็ตาม) เพื่อจะไม่ไป visit ซ้ำอีก กรรมวิธีนี้อาศัยstack ของระบบในการช่วยจัดการทำงาน เนื่องจากจะมีการค้นหาลึกเข้าไปเรื่อยๆ แล้วค่อยย้อนมาคิดหนทางที่ยังค้างไว้ในภายหลัง เราจึงเรียกอัลกอริธึมแบบนี้ว่า depth-first search

วิธี Breadth First Traversal

การท่องแบบกว้าง (Breadth First Traversal) วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟแทนที่จะอาศัยสแต็กเพื่อลุยหาเส้นทางย่อยจากเส้นหลัก เราอาจจะเริ่มที่ว่าเส้นทางออกจากโหนดต้นทางมีกี่เส้นทาง จากนั้นค่อยลุยหาต่อจากโหนดที่เชื่อมถัดไปนั้นจนกว่าจะพบจุดหมาย (หากซ้ำกับเส้นทางเดิมบางส่วนแล้วก็จะยกเลิกหรือตัดออกไป) กรรมวิธีนี้เราสามารถใช้คิวในการจัดการเก็บได้ เราจึงเรียกวิธีนี้ว่า breadth-first search

1. เริ่มต้นที่แถวประจำโหนด(visit C) จากนั้นหาสมาชิกที่มีความสัมพันธ์ ซึ่งจะได้ C->A C->B C->D C->E ได้คำตอบแรกทันทีคือ C->E

2. ในกรณีที่ยังแก้ปัญหาไม่ได้ เราจะเก็บ เก็บ A B D ลงคิวในการทำแต่ละครั้ง ซึ่งตัวที่เคย visit แล้วเราจะไม่นำมาพิจารณาให้เสียเวลาต่อไปอีกในครั้งถัดไป กรรมวิธีนี้จะทำให้ได้เส้นทางที่ดีที่สุดเส้นเดียวออกมา

3. ทั้งนี้ หากต้องการหาเส้นทางที่เป็นไปได้ทั้งหมด เราอาจค้นหาต่อไปได้อีกโดยการใช้แฟล็ก (หรือจดจำตัวที่เคย visit แล้ว โดยจำเป็นลิสต์ของหนทาง และใช้ flag ประจำเส้นทางเพื่อกันไม่ได้มีการวนเส้นทางซ้ำก็อาจจะเป็นไปได้

Direct graph เป็นกราฟที่มีความสัมพันธ์ไปในทิศทางเดียว ดังรูป

เนื่องจากอัลกอริธึมค้นหาเส้นทางเป็นแบบมีทิศทาง เรายังสามารถใช้วิธีการเดิมในการหาเส้นทางได้เช่นเดียวกัน ให้สังเกตว่าตัว adjacency matrix ที่เปลี่ยนไป จะมีผลต่อผลลัพธ์ที่เกิดขึ้น
เรายังคงสามารถใช้ adjacency matrix แทนได้ โดยพิจารณาความสัมพันธ์แบบทางเดียวโดยให้ความสัมพันธ์จากหัวแถวบอกจุดเริ่มต้นดังเช่น

บทที่8

การเรียงลำดับ ( Sorting )

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

ประเภทของการจัดเรียงลำดับข้อมูล

การจัดเรียงลำดับข้อมูลในระบบคอมพิวเตอร์ สามารถแบ่งออกได้เป็น 2 ประเภทใหญ่ๆ คือ

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

2. การจัดเรียงลำดับภายนอก (External Sorting) เป็นการจัดเรียงลำดับข้อมูลที่เก็บอยู่ในสื่อบันทึกข้อมูล โดยทั่วไปข้อมูลที่บันทึกนี้ มักมีจำนวนมากจนไม่สามารถจะเก็บเอาไว้ในหน่วยความจำได้ทั้งหมด ต้องแบ่งออกเป็นส่วนย่อยๆ แล้วจึงนำมาจัดเรียงในหน่วยความจำ จากนั้นจึงทำการบันทึกกลับลงไปในสื่อสำหรับบันทึกข้อมูลเป็นส่วนๆ ต่อจากนั้นนำส่วนต่างๆ ที่จัดเรียงลำดับเรียบร้อยแล้วมาทำการรวมเข้าด้วยกัน (Merge) สำหรับการเรียงแบบภายนอกนั้น จะต้องคิดถึงเวลาที่สูญเสียไปอันเนื่องจากการถ่ายเทข้อมูลระหว่างเทปหรือดิสก์ กับหน่วยความจำหลักด้วย เวลาที่สูญเสียไปในการถ่ายเทข้อมูลระหว่างหน่วยความจำหลักกับเทป หรือดิสก์จะเป็นตัวระบุความดีเลวของแบบการคำนวณแบบเรียงภายนอก

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

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

ในรอบที่ 1 ทำการเปรียบเทียบข้อมูลเพื่อค้นหาข้อมูลที่มีค่าน้อยที่สุด คือ 22นำไปวางที่ตำแหน่งที่ 1 สลับตำแหน่งกับ 35ในรอบที่ 2 ทำการเปรียบเทียบอีกเพื่อค้นหาค่าที่น้อยที่สุดรองลงมาโดยเริ่มค้นตั้งแต่ตำแหน่งที่ 2 เป็นต้นไปได้ค่าน้อยที่สุดคือ 35นำไปวางที่ตำแหน่งที่ 2 สลับตำแหน่งกับ 67ในรอบต่อไปก็ทำในทำนองเดียวกันจนกระทั่งถึงรอบสุดท้ายคือรอบที่ 7 จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามที่ต้องการการจัดเรียงลำดับแบบเลือกเป็นวิธีที่ง่ายและตรงไปตรงมา แต่มีข้อเสียตรงที่ใช้เวลาในการจัดเรียงนานเพราะแต่ละรอบต้องเปรียบเทียบกับข้อมูลทุกตัว ถ้ามีจำนวนข้อมูลทั้งหมด n ตัว ต้องทำการเปรียบเทียบทั้งหมดรอบเป็นดังนี้รอบที่ 1 เปรียบเทียบเท่ากับ n −1 ครั้งรอบที่ 2 เปรียบเทียบเท่ากับ n – 2 ครั้ง
...
รอบที่ n – 1 เปรียบเทียบเท่ากับ 1 ครั้งn – 1 รอบ และจำนวนครั้งของการเปรียบเทียบในแต่ละจำนวนครั้งของการเปรียบเทียบทั้งหมด
= (n −1) + (n −2) + . . . + 3 + 2 + 1
= n (n −1) / 2 ครั้ง

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

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

จากตัวอย่าง การเปรียบเทียบจะเริ่มเปรียบเทียบจากคู่หลัง ในรอบที่ 1 เปรียบเทียบข้อมูลที่ตำแหน่งที่ 7 กับ 8 ได้ว่า 43 น้อยกว่า 82 ให้ทำการสลับตำแหน่งกันเพื่อให้ค่าที่น้อยกว่าอยู่ก่อนต่อไปเปรียบเทียบข้อมูลตำแหน่งที่ 6 กับ 7 ได้ว่า43 น้อยกว่า 99 ให้ทำการสลับตำแหน่งกันอีก ทำการเปรียบเทียบเช่นนี้ในคู่ต่อไปเรื่อย ๆ จนกระทั่งในรอบที่ 2 ทำการเปรียบเทียบข้อมูลจากคู่หลังมาคู่หน้าเช่นกัน แต่จะเปรียบเทียบถึงตำแหน่งที่ 2เท่านั้นจนกระทั่งได้ค่าต่ำสุดรองลงมาไว้ในตำแหน่งที่ 2 ในรอบต่อไปก็ทำในทำนองเดียวกันจนกระทั่งถึงรอบสุดท้ายคือรอบที่ 7 จะเหลือข้อมูลที่ต้องเปรียบเทียบคู่เดียวคือข้อมูลในตำแหน่งที่ 7 กับ 8เมื่อการจัดเรียงเสร็จเรียบร้อยเราจะได้ข้อมูลที่มีการเรียงลำดับจากน้อยไปมากตามที่ต้องการการจัดเรียงลำดับแบบฟองเป็นวิธีที่ไม่ซับซ้อนมากนัก เป็นวิธีการเรียงลำดับที่นิยมใช้กันมากเพราะมีรูปแบบที่เข้าใจง่าย แต่ประสิทธิภาพการทำงานค่อนข้างต่ำพอ ๆ กับการเรียงลำดับแบบเลือกในหัวข้อที่ผ่านมาถ้ามีจำนวนข้อมูลทั้งหมด n ตัวไม่ว่าข้อมูลเป็นอย่างไรก็ตามต้องทำการเปรียบเทียบทั้งหมด n −1 รอบ และจำนวนครั้งของการเปรียบเทียบในแต่ละรอบเป็นดังนี้

กรณีที่แย่ที่สุดจำนวนครั้งของการเปรียบเทียบดังนี้
รอบที่ 1 เปรียบเทียบเท่ากับ n − 1 คู่
รอบที่ 2 เปรียบเทียบเท่ากับ n − 2 คู่
...
รอบที่ n −1 เปรียบเทียบเท่ากับ 1 คู่จำนวนครั้งของการเปรียบเทียบ
= (n −1) + (n −2) + . . . + 3 + 2 + 1
= n (n −1) / 2 ครั้ง

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

การเรียงลำดับแบบเร็ว (quick sort)

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

จากการเปรียบเทียบข้างต้นในที่สุดก็ได้ตำแหน่งที่วางค่าหลัก 44 ซึ่งข้อมูลจะถูกแบ่งเป็น 2 ส่วน ส่วนที่ 1 ข้อมูลทั้งหมดมีค่าน้อยกว่าค่าหลัก และส่วนที่ 2 ข้อมูลทั้งหมดมีค่ามากกว่าค่าหลัก นำแต่ละส่วนไปดำเนินการเปรียบเทียบในลักษณะเดียวกันจนกระทั่งข้อมูลทั้งหมดเรียงลำดับจากน้อยไปมากตามต้องการการจัดเรียงลำดับแบบเร็วเป็นวิธีที่ค่อนข้างซับซ้อน แต่ประสิทธิภาพการทำงานค่อนสูง เนื่องจากใช้เวลาในการเรียงลำดับน้อย ถ้ามีข้อมูลทั้งหมด n ตัวจำนวนครั้งของการเปรียบเทียบเป็นดังนี้ กรณีที่ดีที่สุด คือ กรณีที่ค่าหลักที่เลือกแบ่งแล้วข้อมูลอยู่ตรงกลางกลุ่มพอดี และในแต่ละส่วนย่อยก็เช่นเดียวกันจำนวนครั้งของการเปรียบเทียบเป็นดังนี้จำนวนครั้งของการเปรียบเทียบ = n log2 n ครั้ง

กรณีที่แย่ที่สุด คือ กรณีที่ข้อมูลมีการเรียงลำดับอยู่แล้ว อาจจะเรียงจากน้อยไปมากหรือจากมากไปน้อย หรือค่าหลักที่เลือกในแต่ละครั้งเป็นค่าหลักที่น้อยที่สุดหรือมากที่สุด จำนวนครั้งของการเปรียบเทียบจะมากที่สุดดังนี้จำนวนครั้งของการเปรียบเทียบ
= (n −1) + (n −2) + . . . + 3 + 2 + 1
= n (n −1) / 2 ครั้ง

การเรียงลำดับแบบแทรก (insertion sort)

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

ถ้ามีจำนวนข้อมูลเป็น n การจัดเรียงแบบแทรกจะมีการจัดเรียงทั้งหมดเท่ากับ n − 1 รอบ จำนวนครั้งของการเปรียบเทียบในแต่ละรอบแตกต่างกันขึ้นอยู่กับลักษณะการจัดเรียงของข้อมูลนั้น กรณีที่ดีที่สุด คือ กรณีข้อมูลทั้งหมดจัดเรียงในตำแหน่งที่ต้องการเรียบร้อยแล้ว กรณีนี้ในแต่ละรอบมีการเปรียบเทียบเพียงครั้งเดียว เพราะฉะนั้นจำนวนครั้งของการเปรียบเทียบเป็นดังนี้จำนวนครั้งของการเปรียบเทียบ = n − 1 ครั้ง

กรณีที่แย่ที่สุด คือ กรณีที่ข้อมูลมีการเรียงลำดับในตำแหน่งที่กลับกัน เช่น ต้องการเรียงลำดับจากน้อยไปมาก แต่ข้อมูลมีค่าเรียงลำดับจากมากไปน้อย จำนวนครั้งของการเปรียบเทียบในแต่ละรอบดังนี้
ในรอบที่ 1 จำนวนครั้งของการเปรียบเทียบเป็น 1 ครั้ง
ในรอบที่ 2 จำนวนครั้งของการเปรียบเทียบเป็น 2 ครั้ง
จำนวนครั้งของการเปรียบเทียบ
= 1 + 2 + 3 + . . . +(n −2) + (n −1)
= n (n −1) / 2

การจัดเรียงลำดับแบบฮีพ(HEAP SORT)

การเรียงข้อมูลโดยอาศัยโครงสร้าง Heap เป็นการเรียงข้อมูลแบบที่ดีที่สุด เพราะเป็น อัลกอริทึมที่ประกันได้ว่าเวลาที่ใช้ไม่ว่าในกรณีใดจะเป็น O(log 2 n) เสมอ โครงสร้าง Heap heap เป็นต้นไม้ไบนารีที่มีคุณสมบัติว่าโหนดใด ๆ ในต้นไม้นั้นจะมีค่าคีย์ใหญ่กว่าค่าคีย์ที่อยู่ใน left son และ right son ของมัน (ถ้าโหนดนั้นมีลูก) ตัวอย่างดังรูป (ก) เป็น heap ส่วนรูป (ข) ไม่ใช่ heap

รูป การเปรียบเทียบระหว่างโครงสร้าง Heap กับโครงสร้างอื่น

จาก นิยามของโครงสร้าง heap เราทราบว่ารูตโหนดของ heap จะเป็นโหนดที่มีค่าคีย์ใหญ่กว่า ดังนั้นจากอันพุตที่กำหนดให้เราต้องสร้าง heap ขึ้นก่อน แล้วทำการเอาต์พุตรูตโหนดก็จะได้ค่าแรก (ค่าใหญ่ที่สุด) ของชุดที่เรียงแล้ว ในกรณีนี้จะเรียงจากมากไปน้อย(อัลกอริทึมที่เราอธิบายถึงจะได้ค่าที่เรียง แล้วจากน้อยไปมาก) หลังจากที่เอาต์พุตค่ารูตโหนดไปแล้ว ต้นไม่ที่เหลืออยู่จะไม่เป็น heap เราต้องมีวิธีการตกแต่งหรือปรับแต่งให้ต้นไม้ที่เหลืออยู่นั้นเป็น heap จะได้เอาต์พุตค่าถัดไปได้ ดังนั้นกระบวนการใหญ่ของการทำ heap sortประกอบด้วย 3 ขั้นตอนดังนี้
ขั้นที่ 1 สร้างโครงสร้าง heap
ขั้นที่ 2 เอาต์พุตคีย์ที่รูตโหนด
ขั้นที่ 3 ปรับแต่งต้นไม่ที่เหลือให้เป็น heap

การสร้างโครงสร้าง Heap จากชุดอินพุต อาร์เรย์ใด ๆ สามารถถูกตีความเป็นต้นไม้ไบนารีได้ เช่น อาร์เรย์ที่มีค่าดังนี้

ความสัมพันธ์ระหว่างโครงสร้างอาร์เรย์และโครงสร้าง Heap จะมีรูปเป็นต้นไม้ไบนารีดังรูป

รูปต้นไม้ไบนารีของอาร์เรย์

การสร้าง Heap จะสร้างจากค่าอาร์เรย์ที่อ่านเข้ามาทีละค่าโดยจะสร้าง heap ขนาดที่มี I -1 โหนด เมื่อรับอีกโหนดเข้ามาก็จะได้ heap ที่มีขนาด I ทำเรื่อย ๆ จนได้ heap ขนาด n การอินพุตค่าใหม่เข้าไปใน heap ให้ถูกตำแหน่งค่าตามในต้นไม้ไบนารี หลักการมีดังนี้ (ให้ I เป็นพอยน์เตอร์ชี้ไปยังโหนด Knew)
ขั้นที่ 1 ให้เปรียบเทียบโหนดที่เข้าใหม่กับโหนดที่เป็นพ่อ
IF Knew > K FATHER THEN แลกที่กัน เลื่อน I ไปชี้ยังตำแหน่ง FATHER (นั่นคือ I ติดตาม Knew ขึ้นไป)
ขั้นที่ 2 ทำขั้นที่ 1 เรื่อย ๆ จนทำไม่ได้

ต้นไม้ที่เห็นระหว่างการสร้าง heap นั้น เป็นการตีความข้อมูลในอาร์เรย์ ส่วนความสัมพันธ์ระหว่างพ่อ - ลูก เป็นแบบที่กล่าวมาแล้วข้างต้น หลังจากที่ข้อมูลเรียงในรูปโครงสร้าง heap แล้ว เราจะเอาเอาต์พุตค่ารูตโหนดซึ่งอยุ่ที่ตำแหน่งที่ 1 ในอาร์เรย์ การเอาต์พุตเราจะให้ค่าA(1) แลกที่กับค่าสุดท้ายของอาร์เรย์ A(8) การแทนในรูปต้นไม้ ค่าที่เอาต์พุตไปแล้วจะแทนโดยโหนดสี่เหลี่ยม ต้นไม้ที่ได้ (ไม่นับโหนดสี่เหลี่ยม) ไม่เป็นโครงสร้าง heap จากนี้ต่อไปเราต้องใช้อัลกอริทึมปรับค่าคีย์ต่าง ๆ ในต้นไม้ให้คุณสมบัติ heap การปรับต้นไม้ที่ได้จากการแลกค่าให้มีคุณสมบัติ Heap การปรับแต่งทำได้โดยเลื่อนค่าที่รูตโหนดจากบนลงมาล่าง ดังนี้
ขั้นที่ 1 ให้ตั้งค่าพอยน์เตอร์ I ชี้ไปยังรูตโหนด
ขั้นที่ 2 ให้เลือกค่าที่ใหญ่ที่สุดระหว่าง left son และ right sonของโหนด I เป็นค่าที่เลื่อนมาอยู่ที่ตำแหน่ง I ส่วนค่าคีย์ที่ตำแหน่ง I ก็เลื่อนไปอยู่ที่ตำแหน่ง left son และ right son ของมันที่มีค่าใหญ่กว่า จากนั้นเลื่อนพอยน์เตอร์ I มาอยู่ที่ตำแหน่งใหม่นี้
ขั้นที่ 3 ทำขั้นที่ 2 จนกว่าจะทำไม่ได้

รูปการปรับต้นไม้ให้มีคุณสมบัติ Heap

แสดงถึงการเลื่อนค่า 22 ลงไปยังตำแหน่งถูกต้องของมัน เพื่อที่ทำต้นไม้ที่ได้เป็น heap เมื่อต้นไม้เป็นไปตามรูป (ค) ต้นไม้นั้นจะเป็น heap ซึ่งมีค่าสูงสุด 42 อยู่ที่รูตโหนด เราจะเอาต์พุต 42ไปอยู่ที่ตำแหน่งสุดท้ายของอาร์เรย์ (ตำแหน่งก่อนค่า 90 ไป 1ตำแหน่ง) ดังรูป (ก) ส่วนค่าที่อยู่ที่ตำแหน่งนั้น (ค่า 27) ก็ไปอยู่ที่ตำแหน่ง A(1) หรือรูตโหนด จากนั้นก็เริ่มต้นปรับแต่งต้นไม้ใหม่ให้เป็น heap ซึ่งเริ่มโดยตั้งค่า I ชี้ไปยังรูตโหน

ประเภทของ Heap จะมีอยู่ 2 ประเภท คือ

1. Max heap คือ ประเภทของโหนดลูกแต่ละโหนดจะเก็บข้อมูลที่มีค่าน้อยกว่าหรือเท่ากับข้อมูลใน โหนดพ่อโดยเฉพาะข้อมูลที่ตำแหน่งรูตโหนดจะมีค่ามากที่สุด

2. Min heap คือ โหนดลูกแต่ละโหนดจะเก็บข้อมูลที่มีค่ามากกว่าหรือเท่ากับข้อมูลในโหนดพ่อแม่ โดยเฉพาะข้อมูลที่ตำแหน่งรูตโหนดจะมีค่าน้อยที่สุด
เงื่อนไขของการแตกกิ่งก้านสาขาของโหนด คือ
1. ทุกระดับชั้นของ heap จะแตกสาขาออกได้สองทางคือ ซ้ายและขวา การแตกโหนดจะแตกจากทางซ้ายก่อน และต้องมีโหนดในระดับรูตโหนดครบ 2 ด้านก่อนจึงจะแตกโหนดต่อไปในระดับล่างได้
2. ค่าของโหนดที่เป็นรูตโหนดของ heap จะเป็นโหนดที่มีค่าใหญ่กว่าโหนดตัวล่าง

การสร้าง Heap

จากนิยามของโครงสร้าง heap เราทราบว่ารูตโหนดของ heap จะเป็นโหนดที่มีค่าคีย์ใหญ่กว่า ดังนั้นจากอันพุตที่กำหนดให้เราต้องสร้าง heap ขึ้นก่อน แล้วทำการเอาต์พุตรูตโหนดก็จะได้ค่าแรก (ค่าใหญ่ที่สุด) ของชุดที่เรียงแล้ว ในกรณีนี้จะเรียงจากมากไปน้อย(อัลกอริทึมที่เราอธิบายถึงจะได้ค่าที่เรียง แล้วจากน้อยไปมาก) หลังจากที่เอาต์พุตค่ารูตโหนดไปแล้ว ต้นไม่ที่เหลืออยู่จะไม่เป็น heap เราต้องมีวิธีการตกแต่งหรือปรับแต่งให้ต้นไม้ที่เหลืออยู่นั้นเป็น heap จะได้เอาต์พุตค่าถัดไปได้ ดังนั้นกระบวนการใหญ่ของการทำ heap sort ประกอบด้วย 3 ขั้นตอนดังนี้
ขั้นที่ ขั้นที่ 1 สร้างโครงสร้าง heapขั้นที่ 2 เอาต์พุตคีย์ที่รูตโหนด
ขั้นที่ ขั้นที่ 3 ปรับแต่งต้นไม่ที่เหลือให้เป็น heap

ตัวอย่าง ข้อมูลเริ่มต้นของฮีพ

1. สลับค่าโหนดราก คือ 100 กับค่าโหนดสุดท้ายคือ 7

2. สลับ 36 กับ 2

3. สลับ 25 กับ 1

4. สลับ 19 กับ 2

5. สลับ 17 กับ 2

6. สลับ 7 กับ 1

7. สลับ 3 กับ 2

8. สลับ 2 กับ 1

เหลือโหนดเดียวไม่ต้องปรับฮีพ

วิธีการเรียงลำดับแบบฮีพ โดยแทนฮีพพด้วย Array แสดงในรูป

	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
ฮีพเริ่มต้น	100	19	36	17	3	25	1	2	7
1. สลับ 100 กับ 7	7	19	36	17	3	25	1	2	100
ปรับฮีพ	36	19	25	17	3	7	1	2	100
2. สลับ 36 กับ 2	2	19	25	17	3	7	1	36	100
ปรับฮีพ	25	19	7	17	3	2	1	36	100
3. สลับ 25 กับ 1	1	19	7	17	3	2	25	36	100
ปรับฮีพ	19	17	7	1	3	2	25	36	100
4. สลับ 19 กับ 2	2	17	7	1	3	19	25	36	100
ปรับฮีพ	17	3	7	1	2	19	25	36	100
5. สลับ 17 กับ 2	2	3	7	1	17	19	25	36	100
ปรับฮีพ	7	3	2	1	17	19	25	36	100
6. สลับ 7 กับ 1	1	3	2	7	17	19	25	36	100
ปรับฮีพ	3	1	2	7	17	19	25	36	100
7. สลับ 3 กับ 2	2	1	3	7	17	19	25	36	100
ปรับฮีพ	2	1	3	7	17	19	25	36	100
8. สลับ 2 กับ 1	1	2	3	7	17	19	25	36	100
ปรับฮีพ	1	2	3	7	17	19	25	36	100
สิ้นสุดการเรียงลำดับ	1	2	3	7	17	19	25	36	100

การเรียงลำดับแบบผสาน(Merge Sort)

เป็นขั้นตอนวิธีในการเรียงลำดับที่อาศัยการเปรียบเทียบ และยังเป็นตัวอย่างขั้นตอนวิธีที่ใช้หลักการแบ่งแยกและเอาชนะทำให้ชั้นตอนวิธีนี้มีประสิทธิภาพ O(n log n) ในการอิมพลิเมนต์เพื่อการใช้งานจริง ๆ นั้นสามารถทำได้ทั้งแบบบนลงล่าง (Top-down) และแบบล่างขึ้นบน (Bottom-up) อนึ่งในการอิมพลิเมนต์โดยทั่วไปแล้วการเรียงแบบนี้จะไม่ศูนย์เสียลำดับของข้อมูลที่มีค่าเท่ากัน นั่นคือเป็นการเรียงที่เสถียร

ขั้นตอนวิธีอาศัยหลักการแบ่งแยกและเอาชนะและการเวียนบังเกิด โดยมีรายละเอียดดังนี้

(ขั้นตอนการแบ่ง) สมมติว่ามีข้อมูลอยู่ n ชุด
1. ถ้ามีข้อมูลแค่ 1 ชุด นั่นคือข้อมูลนั้นเรียงลำดับแล้ว
2. ถ้ามีข้อมูลมากกว่านั้น ให้แบ่งเป็นสองส่วน แล้วทำการเวียนบังเกิด
(ขั้นตอนเอาชนะ) เมื่อถึงขั้นตอนนี้จะได้ข้อมูลสองส่วน (โดยที่แต่ละส่วนเรียงในส่วนของตัวเองเรียบร้อยแล้ว) ทำการรวมข้อมูลทั้งสองส่วนนั้นให้เป็นข้อมูลก้อนเดียวที่ทั้งก้อนนั้นเรียงลำดับแล้ว ในการเรียงลำดับข้อมูลทั้งสิ้น n ชุด การเรียงลำดับแบบผสาน มีประสิทธิภาพในกรณีดีที่สุด (โดยมิได้ใส่เงื่อนไขพิเศษ) กรณีเฉลี่ย และกรณีแย่สุด เท่ากันคือ O(n log n) โดยจะแสดงให้ดูดังนี้ สมมติให้เวลาที่ใช้ในการเรียงข้อมูล n ชุด แทนด้วย T(n) เนื่องจาก การเรียงลำดับแบบผสาน มีสองขั้นตอนโดยขั้นแรกคือการแบ่งเป็นสองส่วนซึ่งสามารถทำได้ในเวลาคงที่แต่จะต้องเวียงบังเกิดเรียกตัวเองลงไปแก้ปัญหาที่เล็กลงครึ่งหนื่งสองปัญหา จะได้ว่าในส่วนแรกใช้เวลา 2T(n/2) และขั้นที่สองซึ่งเป็นการผสานข้อมูลสองชุดที่เล็กกว่า (ที่เรียงในตัวเองแล้ว) เป็นข้อมูลชุดใหญ่จะใช้เวลาอีก n ดังที่ได้แสดงให้ดูในตัวอย่างการอิมพลิเมนต์ด้านบน เมื่อรวมทั้งสองขั้นแล้วจะใช้เวลาทั้งสิ้น T(n) = 2T(n/2) + n หากใช้ Master Theorem ในการวิเคราะห์สมการนี้จะได้ผลลัพทธ์เป็น O(n log n) ดังที่ได้กล่าวไว้

โครงสร้างข้อมูลและขั้นตอนวิธีเพื่องานธุรกิจ

วันอังคารที่ 26 เมษายน พ.ศ. 2559

บทที่6