DTS_10 09/09/2552

สรุปบทเรียนเรื่อง Sorting

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

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

- การเรียงลำดับแบบเลือก (selection sort)เป็นการเลือกข้อมูลที่มี
ค่ามากหรือน้อยที่สุดไปเก็บไว้ในตำแหน่งที่ 1 แล้วก็ทำแบบเดิมไปเรื่อยๆฃ
นกระทั่งครบทุกข้อมูลก็จะได้ลำดับจากน้อยไปมากหรือมากไปน้อยตามที่ต้องการ
- การเรียงลำดับแบบฟอง (Bubble Sort)เป็นการเรียงลำดับโดยการเลือก
คู่ข้อมูลจากหน้าหรือหลังก็ได้แล้วก็เลือกว่าจะเรียงจากน้อยไปมากหรือมากไปน้อย
โดยการเปรียบเทียบข้อมูลที่เลือกทั้งสองตัวแล้วสลับตำแหน่งกันเพื่อจะได้นำ
ไปเปรียบเที่ยบในตำแหน่งต่อไปจนครบ
- การเรียงลำดับแบบเร็ว (quick sort)
-การเรียงลำดับแบบแทรก (insertion sort)เป็นการเรียงลำดับข้อมูล
แบบเลือกคู่ข้อมูลจากหน้าหรือหลังก็ได้แล้วนำข้อมูลถัดไปมาเปรียบเทียบกัน
ระหว่างข้อมูลทั้งสองว่าจะวางในตำแหน่งใดทำจนครบทุกข้อมูล
- การเรียงลำดับแบบฐาน (radix sort)เป็นการเรียงลำดับโดยพิจารณา
จากฐานตัวเลขโดยเริ่มจาก 0 ถึง9 โดยรอบแรกให้พิจารณาในหลักหน่วยและ
เรียงลำดับหลักไปจนครบตามจำนวนข้อมูลก็จะได้เลขที่เรียงลำดับโดยอัตโนมัติ

DTS_ 9 02/09/2552

สรุปเรื่อง ทรี Tree (ต่อ)

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

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

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

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

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

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

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

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


เรื่อง Graph

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

นิยามของกราฟ

กราฟเป็นโครงสร้างข้อมูลแบบไม่ใช้เชิงเส้นที่ประกอบด้วยกลุ่ม
ของสิ่งสองสิ่งคือ
1.โหนด (Nodes) หรือ เวอร์เทกซ์ (Vertexes)
2.เส้นเชื่อมระหว่างโหนดเรียก เอ็จ (Edges)
กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด ถ้าเอ็จไม่มีลำดับ
ความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง
(Undirected Graphs) และถ้ากราฟนั้นมีเอ็จที่มีลำดับ
ความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า
กราฟแบบมีทิศทาง (Directed Graphs) บางครั้งเรียกว่า
ไดกราฟ (Digraph)
การเขียนกราฟแสดงโหนดและเส้นความสัมพันธ์ ระหว่างโหนด
ไม่มีรูปแบบที่ตายตัว

ตัวอย่างรูปแบบของกราฟ

โหนดสองโหนดในกราฟแบบไม่มีทิศทางถือว่าเป็นโหนดที่ใกล้
กัน (Adjacent) ถ้ามีเอ็จเชื่อมจากโหดนที่หนึ่งไปโหนดที่สอง
กราฟ(ก) แสดงกราฟที่มีลักษณะต่องเนื่อง (Connected)
เป็นกราฟที่มีเส้นทางเชื่อมจากโหนดใดๆไปยังโหนดอื่นเสมอ