DTS09/19/2009

Sorting ถ้าเราจำเป็นต้องเก็บและค้นหาข้อมูลอยู่เป็นประจำ การเก็บข้อมูลเราก็ต้องจัดเก็บให้เป็นระเบียบและง่ายในกระบวนการค้นหาข้อมูลเพื่อนำมาใช้ใหม่ เช่นการจัดเรียงหมวดหมู่ของหนังสือในห้องสมุดต้องมีการจัดการรายละเอียดของหนังสื่อต่างๆ ให้เป็นแฟ้มข้อมูลที่เรียงลำดับตามอักษร เป็นต้น และในการประกอบการต่างๆ ที่เกี่ยวข้องกับการใช้งานด้านคอมพิวเตอร์ก็มีการจัดเรียงลำดับของข้อมูลโดยวิธีใดวิธีหนึ่งแล้วแต่เรากำหนดทำไมเราจึงต้องศึกษาการเรียงลำดับข้อมูล (Sorting) เพื่อช่วยในการออกแบบอัลกอรึทึม เพราะการเรียงลำดับข้อมูล เป็นงานพื้นฐานที่ใช้ในโปรแกรมประยุกต์ต่างๆ ช่วยทำให้การเรียกใช้งานข้อมูลนั้นๆ มีความสะดวก รวดเร็ว ในการค้นหา มากกว่าการเรียกใช้ข้อมูลที่ไม่มีการลำดับ และทำให้เกิดเทคนิคใหม่ๆ ที่น่าสนใจและสำคัญอันได้แก่ Partial ,order ,recursion ,merge ,lists การจัดเก็บ

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

การเรียงข้อมูล สามารถแบ่งได้เป็น 2 ประเภทด้วยกันคือ

1. การเรียงข้อมูลแบบภายใจ (Intemal sorting) คือการเรียงลำดับข้อมูลโดยทั้งหมดต้องจัดเก็บอยู่ในหน่วยความจำหลัก (main memory) ที่มีการเข้าถึงข้อมูลได้เร็วโดยไม่จำเป็นต้องใช้หน่วยความจำสำรอง เช่นดิสก์ หรือเทปสำหรับการจัดเก็บชั่วคราว ใช้ในกรณีที่ข้อมูลไม่มากเกินกว่าพื้นที่ความจำเป็นกำหนดให้กับผู้ใช้

แต่ละราย

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

อัลกอรึทึมสำหรับการเรียงข้อมูล จัดได้ 3 ประเภทใหญ่ๆ คือ

1. การเรียงลำดับแบบแลกเปลี่ยน (Exchange sort)

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

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

Sorting Algorithms

Bubble sort

หลักของการเรียงแบบนี้คือ จะเปรียบเทียบและแลกแปลี่ยนข้อมูล 2 ค่าที่อยู่ติดกันในลักษณะที่เรากำหนดเช่นจากน้อยไปหามาก หรือ จากมากไปหาน้อย โดยจะทำการเปรียบเทียบข้อมูลทั้งชุดจนกว่าจะมีการเรียงลำดับทั้งหมดของขั้นตอนการทำงานของอัลกอรึทึม

Quick Sort

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

Insertion Sort

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

DTS08/13/09/2009

Graph กราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง Vertex และ Edge กราฟจะประกอบด้วยกลุ่มของ Vertex ซึ่งจะแสดงในกราฟด้วยสัญญลักษณ์รูปวงกลมและกลุ่มของ Edge

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

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

G=(V,E)

G คือ กราฟ

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

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

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

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

แบ่งเป็น 3 ประเภทโดยแบ่งตามประเภทของ egdg คือ

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

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

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

เส้นเชื่อมต่อระหว่าง vertex อาจจะแสงทิศทางหรือไม่แสดงทิศทางการเชื่อมต่อก็ได้

เส้นทาง (Path)

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

vertex หนึ่งไปยังอีก vertex หนึ่งถ้าหากเส้นทางประกอบด้วย vertex จำนวน N ความยาวของเส้นทางจะเท่ากับ N-1

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

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

N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N*N โดยค่าในเมตริกซ์จะประกอบด้วย ค่า 0 และ 1

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

DTS07/01/09/2009

tree หรือ โครงสร้างข้อมูลแบบต้นไม้ ประกอบด้วยโหนด (Node) ซึ่งเป็นส่วนที่เก็บข้อมูลในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดก็สามารถแตกโหนดออกเป็นโหนด
ย่อยๆได้อีกหลายโหนดเรียกกันว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent node) โดยการแตกโหนดออกเป็นโหนดย่อยๆ ได้อีก

Root Node จากรูป คือ โหนด A
Child Node หรือ โหนดลูก จากรูป B,C,D และ E เป็นโหนดลูกของ A
Parent Node หรือโหนดพ่อแม่ โหนด B ที่เป็นโหนดลูกของโหนด A ก็สามารถแตกออกเป็นโหนดย่อยๆได้แก่ F และ G ดัง นั้น B จึงเป็นโหนดพ่อแม่ของ F และ G ในทำนองเดียวกัน A ก็นเป็นโหนดพ่อแม่ของ
B,C,D และ E กิ่ง (branch or Edge) เป็นเส้นที่เชื่อมต่อระหว่างโหนดพ่อแม่กับโหนดลูก Brother node หรือโหนดพี่น้อง คือ โหนดที่มีพ่อแม่เดียวกัน เช่น B,C,D,E เป็นโหนดพี่น้องกันเพราะมีโหนดพ่อแม่เดียวกัน คือ โหนด A และ F และ G เป็นโหนดพี่น้องกันโดยมี B เป็นโหนดพ่อแม่
Leaf node คือ โหนดที่ไม่มีโหนดลูก จากรูปโหนดที่ไม่มีโหนดลูกได้แก่ F G H K J K L M
Baranch node คือ โหนดที่ไม่ใช่ Leaf node เช่น โหนด B C D E เรียกว่า Branch node
Degree คือ จำนวนลูกของโหนด x เช่น degree ของโหนด A = 4 ได้แก่ B C D E จำนวน degree ของโหนด B=2 จำนวน degree ของโหนด F=0 เนื่องจากโหนด F ไม่มีโหนดลูก
Direct Descendant node คือ โหนดที่มาทีหลังทันที จากรป B C D E เป็น direct descendant node ของโหนด A เพราะเป็นโหนดที่มาทีหลังทันที
Descendant node คือ โหนดลูกของโหนด x และโหนดที่ทุกโหนดที่แตกจากโหนดลูกของโหนด x ตัวอย่าง descendant ของโหนด A คือ ทุกโหนดที่เหลือในทรี

Binary tree มีลักษณะเหมือนกับ tree ปกติแต่มีคุณสมบัติพิเศษ คือ แต่ละโหนดจะมีโหนดลูกได้ไม่เกิน 2 โหนด หรือพูดอีกอย่างหนึ่งว่า แต่ละโหนดใน binary tree จะมีดีกรีได้ไม่เกิน 2

Complete Binary Tree
หรือต้นไม้ใบนารีแบบสมบูรณ์ มีลักษณะคล้ายกับ Binary Tree แต่มีข้อพิเศษ คือ
1. ทุกโหนดที่ไม่ใช่ Leaf node จะต้องมีโหนดลูก 2 โหนด
2. Leaf node จะต้องอยู่ในระดับเดียวกัน

Binary Search Tree
จะมีลักษณะคล้ายกับ Binary Tree แต่มีลักษณะพิเศษเพิ่มเติม คือ
1. ค่าของรูทโหนดมีค่ามากกว่าค่าในต้นไม้ย่อยซ้าย

2. ค่าของรูทโหนดมีค่าน้อยกว่าหรือเท่ากับในต้นไม่ย่อยขวา

การท่องไปในทรี (Tree Traversal)

สามารถท่องเข้าไปในทรีเพื่อดูข้อมูลได้ 3 วิธีด้วยกัน คือ

1. Preorder

2. inorder

3. postorder

ในการท่องเข้าไปในทรีแต่ละแบบจะใช้สัญลักษณ์ดังนี้ Root = root node left = ต้นไม้ย่อยซ้ายของ

Root Right = ต้นไม้ย่อยขวาของ Root

วิธีการท่องเข้าไปในทรีแต่ละทรีแต่ละแบบจะมีลักษณะดังนี้

1. Preorder = Root Left Right

2. Inorder = Left Root Right

3. Postorder = Left Right Root

ตัวอย่างแสดงการท่องไปในทรี