DTS11-16-09-2552

สรุปสิ่งที่ได้จากการเรียนเรื่อง SORTING (ต่อ)

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

DTS10-09-09-2552

สรุปสิ่งที่ได้รับในการเรียนเรื่อง SORTING

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

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

การจัดเรียงข้อมูลแบบเบื้องต้น

1. การจัดเรียงข้อมูลแบบเลือก (Selection Sort) มีหลักการของการจัดเรียง คือ เลือกค่าข้อมูลที่น้อยหรือมากที่สุดอย่างใดอย่างหนึ่งในแต่ละฐานข้อมูลเป็นตัวหลัก จากนั้นนำมาจัดเรียงแบบลำดับเลือกข้อมูลตัวต่อไปจนจัดเรียงเสร็จ เช่น ข้อมูล 1 ชุด ประกอบด้วย 390 205 182 45 235 จากข้อมูลชุดนี้ หากนำมาจัดเรียงแบบเลือกจัดลำดับค่าต่ำสุดไปหาค่าสูงสุดได้ดังนี้จากตารางแสดงการจัดเรียงข้อมูลแบบเลือกของชุดข้อมูลทั้ง 5 ตัวในแนวตั้ง คือ
ครั้งที่ 1 เลือกข้อมูลที่มีค่าน้อยที่สุดมาจัดเรียงลำดับสลับตำแหน่งระหว่าง 45 และ 390
ครั้งที่ 2 เลือกข้อมูลที่น้อยลงมาเป็นอันดับที่ 2 คือ 182 ไปสลับกับ 205 ในตำแหน่งที่ 2
ครั้งที่ 3 เลือกข้อมูลที่น้อยลงมาเป็นอันดับที่ 3 คือ 205 ซึ่งอยู่ในตำแหน่งเดิม
ครั้งที่ 4 เลือกข้อมูลที่น้อยลงมาเป็นอันดับที่ 4 คือ 235 ไปสลับกับ 390 ในตำแหน่งที่ 4
จึงไม่มีครั้งที่ 5 เพราะข้อมูลได้มีการจัดเรียงลำดับครบทุกตัวแล้ว

2. การจัดเรียงข้อมูลแบบฟอง (Bubble Sort) เป็นรูปแบบของการจัดเรียงแบบแลกเปลี่ยนเนื่องจากลักษณะของการจัดเรียงจะใช้การเปรียบเทียบค่าใน 2 ตำแหน่งใกล้เคียงเรียงลำดับการจัดจากมากไปน้อยหรือจากน้อยไปมาก จากนั้นจะเปลี่ยนตำแหน่งกันแล้วใช้ตำแหน่งที่ 2 เปรียบเทียบกับตารางที่ 3 ไปจนถึงตำแหน่งที่ n จนเสร็จสิ้นการจัดเรียง เช่น จากข้อมูล 390 205 182 45 235 นำมาจัดเรียงแบบบับเบิ้ลได้ดังตาราง

จากตารางแสดงการจัดเรียงข้อมูลแบบบับเบิ้ลในรอบที่ 1 ทำการเปรียบเทียบค่าแล้วเลื่อนค่าลงเปรียบเทียบกับตำแหน่งต่อไป ในรอบที่ 1 นี้จะทำการเปรียบเทียบอยู่ 4 ครั้ง คือ
ครั้งที่ 1 เปรียบเทียบข้อมูลกับตำแหน่งที่ 1,2 ข้อมูล 390>205 เปลี่ยนตำแหน่ง 205 ไว้ด้านบน
ครั้งที่ 2 เปรียบเทียบข้อมูลกับตำแหน่งที่ 2,3 ข้อมูล 390>182 เปลี่ยนตำแหน่ง 182 ไว้ด้านบน
ครั้งที่ 3 เปรียบเทียบข้อมูลกับตำแหน่งที่ 3,4 ข้อมูล 390>45 เปลี่ยนตำแหน่ง 45 ไว้ด้านบน
ครั้งที่ 4 เปรียบเทียบข้อมูลกับตำแหน่งที่ 4,5 ข้อมูล 390>235 เปลี่ยนตำแหน่ง 235 ไว้ด้านบน
จะเห็นว่าข้อมูลที่จัดเรียงได้ค่า 205 182 45 235 390 ซึ่งยังไม่เสร็จสิ้น จึงต้องทำการเปรียบเทียบค่าอีกโดยใช้วิธีการเดิมในรอบที่ 2

ข้อมูลที่ได้จากการจัดเรียงในรอบที่ 2 คือ 182 45 205 235 390 ซึ่งในรอบนี้จะเห็นว่าการเปรียบเทียบค่านั้นจะเปรียบเทียบเพียงแค่ 2 ครั้งเพราะค่าหลัง 205 นั้นมีค่ามากกว่าแล้วจึงไม่ดำเนินการต่อแต่ยังต้องเรียงลำดับข้อมูลต่อในรอบที่ 3

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

3. การจัดเรียงข้อมูลแบบแทรก (Insertion Sorting) จะใช้หลักการของการจัดเรียงที่ว่ากำหนดพื้นที่ออกเป็น 2 ส่วน ส่วนแรกใช้ในการจัดข้อมูลที่เรียงลำดับแล้วและอีกส่วนคือ ข้อมูลที่ยังไม่ได้จัดเรียง นำเอาข้อมูลที่ยังไม่ได้จัดเรียงมาแทรกยังตำแหน่งที่ถูกต้องด้านที่ใช้จัดเรียงลำดับ และดำเนินการต่อไปจนกว่าการจัดเรียงจะถูกต้อง เช่น ข้อมูลชุด 23 78 45 8 32 56 สามารถจัดเรียงได้ดังภาพ

จากภาพ แสดงการแบ่งพื้นที่ในการจัดเรียงข้อมูลจะกำหนดพื้นที่ส่วนหน้าเป็นพื้นที่จัดเรียงข้อมูล พื้นที่ส่วนหลังใช้ในการเก็บข้อมูลที่ยังไม่ได้จัดเรียง หากนำข้อมูลมาจากพื้นที่ด้านหลังก็จะนำมาแทรกยังตำแหน่งที่ถูกต้องด้านหน้า ซึ่งจะได้ข้อมูลการจัดเรียงแบบถูกต้องคือ 8 23 32 45 56 78

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

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

DTS09-02-09-2552

สรุปสิ่งที่ได้จากการเรียนเรื่อง TREE ( ต่อ )

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

ในการแทนนิพจน์ใน expression tree นั้น operand จะเก็บอยู่ที่โหนดใบ ส่วน operator จะเก็บในโหนดกิ่ง หรือโหนดที่ไม่ใช่โหนดใบ

BINARY SEARCH TREE
เป็นไบนารีทรีที่ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อยก็จะมีคุณสมบัติเช่นเดียวกัน

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

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

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

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


กราฟที่มีการเปลี่ยนแปลงตลอดเวลา ควรใช้วิธี Adjacency List ซึ่งเป็นวิธีที่คล้ายวิธีการจัดเก็บกราฟแบบการเก็บโหนดและพอยน์เตอร์ แต่แตกต่างกันตรงที่จะใช้ลิงค์ลิสต์แทน เพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข มีหลักคือ
- การแทนค่าแต่ละแถวของอะเรย์ 2 มิติจะกลายเป็นลิงค์ลิสต์
- หัวแถวจะเป็นโหนดของกราฟ จะมีเท่ากับจำนวนโหนด
- โหนดในแต่ละแถวคือ โหนดที่อยู่ข้างเคียงหรือเพื่อนบ้านของโหนดหัวแถว
ตัวอย่างเช่น
การแทนที่กราฟด้วยเมทริกซ์ หรือ Adjacency Matrix เป็นโครงสร้างที่ประกอบไปด้วยโหนดและเส้นเชื่อมต่อที่บอกถึงเส้นทางของการเดินทาง หรือความสัมพันธ์ในทิศทางซึ่งสามารถนำมาแทนความสัมพันธ์นั้นด้วยการกำหนดเมตริกซ์ n x n
ตัวอย่างเช่น
สามารแทนที่กราฟแบบเมทริกซ์ได้ดังนี้

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

พิจารณาโหนด A มีเส้นเชื่อมต่อระบุไป B ระบุหมายเลย 1 นอกนั้นระบุค่าเป็น 0
พิจารณาโหนด B มีเส้นเชื่อมต่อระบุไป C, E ระบุหมายเลย 1 นอกนั้นระบุค่าเป็น 0
พิจารณาโหนด C มีเส้นเชื่อมต่อระบุไป D, E ระบุหมายเลย 1 นอกนั้นระบุค่าเป็น 0
พิจารณาโหนด D ไม่มีเส้นเชื่อมต่อไปยังโหนดอื่น B ระบุหมายเลข 0 ทุกช่อง
พิจารณาโหนด E มีเส้นเชื่อมต่อระบุไป D, F ระบุหมายเลย 1 นอกนั้นระบุค่าเป็น 0
พิจารณาโหนด F ไม่มีเส้นเชื่อมต่อไปยังโหนดอื่น B ระบุหมายเลข 0 ทุกช่อง