DTS 10-09/09/52

Sorting

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

(1) เวลาและแรงงาน

(2) เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงาน

(3) จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่

วิธีการเรียงลำดับ

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

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

(2) การเรียงลำดับแบบภายนอก(external sorting) เป็นการเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการ

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

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

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

1. ในรอบแรกจะทำการค้นหาข้อมูลตัวที่มีค่าน้อยที่สุดมาเก็บ

ไว้ที่ตำแหน่งที่ 1

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

ตำแหน่งที่สอง

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

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

รอบเป็นดังนี้

รอบที่ 1 เปรียบเทียบเท่ากับ n - 1 ครั้ง

รอบที่ 2 เปรียบเทียบเท่ากับ n – 2 ครั้ง

รอบที่ n – 1 เปรียบเทียบเท่ากับ 1 ครั้ง

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

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

1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน

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

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

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

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

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

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

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

จำนวนครั้งของการเปรียบเทียบ = n - 1 ครั้งการเรียงลำดับแบบฐาน เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก

1. เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน นั่นคือถ้าข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่วยก่อน

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

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

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

DTS 09-02/09/52

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

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

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

DTS 08-26/08/52

Tree
ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับ ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงานต่าง ๆ ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมูล
แต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆ โหนดเรียกโหนดดังกล่าวว่าโหนดแม่ (Parent or Mother Node)
โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก (Child or Son Node)
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหนดราก (Root Node)
โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings)
โหนดที่ไม่มีโหนดลูก เรียกว่าโหนดใบ (Leave Node)
เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง (Branch)
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest)หมายถึง กลุ่มของทรีเกิดจากการเอาโหนดรากของ
ทรีออกหรือ เซตของทรีที่แยกจากกัน
2. ทรีที่มีแบบแผน (Ordered Tree)หมายถึง โหนดต่าง ๆ ในทรีนั้นมี
ความสัมพันธ์ที่แน่นอน
แสดงทรีที่ต่างกันเมื่อกำหนดให้เป็นทรีที่มีแบบแผน
3. ทรีคล้าย (Similar Tree) คือ โครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) คือ เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree) หมายถึง จำนวนทรีย่อยของโหนด
6. ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนด ที่อยู่ห่างจากโหนดราก กำหนดให้ โหนดรากของทรีอยู่ระดับ 1และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1 หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุด จากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1 และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่างจากโหนดราก เรียกว่า ความสูง (Height) หรือความลึก (Depth)
การแทนที่ทรีในหน่วยความจำหลัก
1. โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด การแทนที่ทรีด้วยวิธีนี้ จะให้จำนวนฟิลด์ในแต่ละโหนดเท่ากันโดยกำหนดให้มีขนาดเท่ากับจำนวนโหนดลูกของโหนดที่มีลูกมากที่สุด โหนดใดไม่มีโหลดลูกก็ให้ค่าพอยเตอร์ในลิงค์ฟิลด์นั้นมีค่าเป็น Null และให้ลิงค์ฟิลด์แรกเก็บค่าพอยเตอร์ชี้ไปยังโหนด ลูกลำดับที่หนึ่ง ลิงค์ฟิลด์ที่สองเก็บค่าพอยเตอร์ชี้ไปยังโหนดลูกลำดับที่สอง และลิงค์ฟิลด์อื่นเก็บค่าพอยเตอร์ของโหนดลูก
ลำดับ ถัดไปเรื่อย ๆ
2. แทนทรีด้วยไบนารีทรี เป็นวิธีแก้ปัญหาเพื่อลดการ สิ้นเปลืองเนื้อที่ในหน่วยความจำก็คือ กำหนดลิงค์ฟิลด์ให้มีจำนวนน้อยที่สุดเท่าที่จำเป็นเท่านั้นโดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์
-ลิงค์ฟิลด์แรกเก็บที่อยู่ของโหนดลูกคนโต
-ลิงค์ฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไป
โหนดใดไม่มีโหนดลูกหรือไม่มีโหนดพี่น้องให้ค่าพอยน์เตอร์ใน
ลิงค์ฟิลด์มีค่าเป็น Null
การท่องไปในไบนารีทรี คือ การท่องไปในไบนารีทรี เพื่อเข้าไปเยือนโหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้งวิธีการท่องไปนั้นมีด้วยกันหลายแบบ
การลำดับขั้นตอนการเยือน โหนดที่ถูกเยือนอาจเป็น เช่น
โหนดแม่ (แทนด้วย N)
ทรีย่อยทางซ้าย (แทนด้วย L)
ทรีย่อยทางขวา (แทนด้วย R)
มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR
วิธีการท่องจากซ้ายไปขวา 3 แบบแรกที่นิยมใช้คือ NLR LNR และ LRN ซึ่งแต่ละลักษณะ มีดังนี้
1. การท่องไปแบบพรีออร์เดอร์(Preorder Traversal)
เป็นการเดินเข้าไปเยือนโหนด ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
- เยือนโหนดราก
- ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
- ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์

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

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

DTS 07-05/08/52

Queue

คิว (Queue) เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสต์ซึ่งการเพิ่มข้อมูลจะกระทำที่ปลายข้างหนึ่งซึ่งเรียกว่าส่วนท้ายหรือเรียร์ (rear) และการนำข้อมูลออกจะกระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า ส่วนหน้า หรือ ฟรอนต์(front)
ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อนออกก่อนหรือที่เรียกว่า FIFO (First In First Out)
การทำงานของคิว
- การใส่สมาชิกตัวใหม่ลงในคิวเรียกว่า Enqueue ซึ่งมีรูปแบบคือ enqueue หมายถึง การใส่ข้อมูล newElement ลงไปที่ส่วนเรียร์ของคิว
- การนำสมาชิกออกจากคิว เรียกว่า Dequeue ซึ่งมีรูปแบบคือ dequeue หมายถึง การนำออกจากส่วนหน้าของคิวและให้ ข้อมูลนั้นกับ element

การแทนที่ข้อมูลของคิว สามารถทำได้ 2 วิธี คือ
1. แบบลิงค์ลิสต์
2. แบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์ จะประกอบไปด้วย 2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 3 ส่วน คือ พอยเตอร์จำนวน 2 ตัว คือ Front และ rear กับจำนวนสมาชิกในคิว
2. Data Node จะประกอบไปด้วย ข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

การดำเนินการเกี่ยวกับคิว
1. Create Queue จัดสรรหน่วยความจำให้แก่ Head Node และ
ให้ค่า pointer ทั้ง 2 ตัวมีค่าเป็น null และจำนวน สมาชิกเป็น 0
2. Enqueue การเพิ่มข้อมูลเข้าไปในคิว
3. Dequeue การนำข้อมูลออกจากคิว
4. Queue Front เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง
5. Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
6. Empty Queue เป็นการตรวจสอบว่าคิวว่างหรือไม่
7. Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่
8. Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว
9. Destroy Queue เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว

การแทนที่ข้อมูลของคิวแบบอะเรย์
- การนำข้อมูลเข้าสู่คิว จะไม่สามารถนำเข้าในขณะที่คิวเต็ม หรือไม่มีที่ว่าง ถ้านำเข้าจะทำให้เกิดความผิดพลาดที่เรียกว่า overflow
- การนำข้อมูลออกจากคิว จะไม่สามารถนำอะไรออกจากคิวที่ว่างเปล่าได้ ถ้าจะทำให้เกิดความผิดพลาดที่เรียกว่า underflow