Park-Kachen
15 กันยายน 2552
DTS10-09-09-2552
Sorting
ถ้าเราจำเป็นต้องเก็บและค้นหาข้อมูลอยู่เป็นประจำ การเก็บข้อมูลเราก็ต้องจัดเก็บให้เป็นระเบียบ และง่ายในกระบวนการค้นหาข้อมูลเพื่อนำมาใช้ใหม่ เช่นการจัดเรียงหมวดหมู่ของหนังสือในห้องสมุด ต้องมีการจัดการกับรายละเอียดของหนังสือต่างๆ ให้เป็นแฟ้มข้อมูลที่เรียงลำดับตามตัวอักษร เป็นต้น
และในการประกอบการต่างๆ ที่เกี่ยวข้องกับการใช้งานด้านคอมพิวเตอร์ ก็มีการจัดเรียงลำดับของข้อมูล โดยวิธีใดวิธีหนึ่งแล้วแต่กำหนดทำไมเราจึงต้องศึกษาการเรียงลำดับข้อมูล (Sorting) เพื่อช่วยในการออกแบบอัลกอรึทึม ?
เพราะการเรียงลำดับข้อมูล เป็นงานพื้นฐานที่ใช้ในโปรแกรมประยุกต์ต่างๆ ช่วยทำให้การเรียกใช้งานข้อมูลนั้นๆ มีความสะดวก รวดเร็ว ในการค้นหา มากกว่าการเรียกใช้ข้อมูลที่ไม่มีการลำดับ และทำให้เกิดเทคนิคใหม่ๆที่น่าสนใจและสำคัญอันได้แก่ partial order , recursion , merge , lists , การจัดเก็บ binary tree ในอาร์เรย์ เป็นต้น
อีกทั้ง อัลกอรึทึมที่ใช้เพื่อการเรียงลำดับข้อมูลแต่ละตัวมีข้อดีและข้อเสียแตกต่างกัน ขึ้นอยู่กับจำนวน ชนิดของข้อมูล การกำหนดค่าเริ่มต้น ขนาด และค่าของข้อมูลที่จะทำการเรียงลำดับ สิ่งสำคัญก็คือ เราต้องรู้ว่าเรามีความต้องการอย่างไรเพื่อที่สามารถจะเลือก อัลกิรึทึมที่มีความเหมาะสม และสอดคล้องกับงานของเราได้...
การเรียงข้อมูล สามารถแบ่งได้เป็น 2 ประเภทด้วยกันคือ
1. การเรียงข้อมูลแบบภายใน (Internal Sorting) คือ การเรียงลำดับข้อมูล โดยทั้งหมดต้องจัดเก็บอยู่ในหน่วยความจำหลัก (main memory) ที่มีการเข้าถึงข้อมูลได้เร็ว โดยไม่จำเป็นต้องใช้หน่วยความจำสำรอง เช่น ดิสค์ หรือเทปสำหรับการจัดเก็บชั่วคราว ใช้ในกรณีที่ข้อมูลไม่มากเกินกว่าพื้นที่ความจำที่กำหนดให้กับผู้ใช้แต่ละราย
2. การเรียงข้อมูลแบบภายนอก (External Sorting) คือ การ เรียงลำดับข้อมูลที่มีขนาดใหญ่เกินกว่าที่จะสามารถเก็บไว้ใน พื้นที่ความจำหลักที่กำหนดให้ได้ในคราวเดียว ดังนั้นข้อมูล ส่วนมากต้องเก็บไว้ในไฟล์ข้อมูลที่อยู่บนดิสค์ เทป เป็นต้น สำหรับการเรียงข้อมูลแบบภายนอกจะต้องคิดถึงเวลาที่ใช้ใน การถ่ายเทข้อมูลจากหน่วยความจำชั่วคราวกับหน่วยความจำหลัก ด้วยเช่นกัน
อัลกอรึทึมสำหรับการเรียงข้อมูล จัดได้ 3 ประเภทใหญ่ๆ ดังนี้
1. การเรียงลำดับแบบแลกเปลี่ยน (Exchange Sort)
2. การเรียนลำดับแบบแทรก (Insertion Sort)
3. การเรียงลำดับแบบเลือก (Selection Sort)
Sorting Algorithms
Bubble Sort หลักของการเรียงแบบนี้คือ จะเปรียบเทียบและแลกเปลี่ยนข้อมูล 2 ค่าที่อยู่ติดกันในลักษณะที่เรากำหนด เช่น จากน้อยไปมาก หรือจากมากไปน้อย โดยจะทำการเปรียบเทียบข้อมูลทั้งชุดจนกว่าจะมีการเรียงตามลำดับทั้งหมดขั้นตอนการทำงานของอัลกอริทึม
Quick Sort การเรียงลำดับในลักษณะนี้ เป็นการปรับปรุงมาจากการเรียงลำดับแบบ Bubble เพื่อให้การเรียงลำดับเร็วขึ้น วีธีนี้เหมาะกับการเรียงข้อมูลที่มีจำนวนมาก หรือมีขนาดใหญ่ และเป็นวิธีการเรียงข้อมูลที่ให้ค่าเฉลี่ยของเวลาน้อยที่สุดเท่าที่ค้นพบวิธีหนึ่งการเรียงลำดับแบบ Quick Sortจะเป็นการเปรียบเทียบสมาชิกที่ไม่อยู่ติดกัน โดยกำหนดข้อมูลค่าหนึ่ง เพื่อแบ่งชุดข้อมูลที่ต้องการเรียงลำดับออกเป้น 2 ส่วน จากนั้นก็จะทำการแบ่งย่อยชุดข้อมูล 2 ส่วนนั้นลงไปอีก ทำแบบนี้ไปเรื่อยๆจนข้อมูลแต่ละชุดมีสมาชิกเหลือเพียงตัวเดียวและทำให้ชุดข้อมูลทั้งหมดมีการเรียงลำดับ
Insertion SortInsertion Sort การเรียงลำดับที่ง่ายไม่ซับซ้อน เป็นการนำข้อมูลใหม่เพิ่มเข้าไปในชุดข้อมูลที่มีการเรียงลำดับอยู่แล้ว โดยข้อมูลใหม่ที่นำเข้ามาจะแทรกอยู่ในตำแหน่งทางขวาของชุดข้อมูลเดิม และยังคงทำให้ข้อมูลทั้งหมดมีการเรียงลำดับวิธีนี้เริ่มต้นโดยการเรียงลำดับข้อมูล 2 ตัวแรกของชุดข้อมูล หลังจากนั้นเพิ่มข้อมูลตัวที่ 3 เข้ามา จะมีการเปรียบเทียบค่ากับข้อมูล 2 ตัวแรก และแทรกอยู่ในตำแหน่งที่เหมาะสม และสำหรับการเพิ่มข้อมูลตัวต่อๆไปก็จะทำเหมือนเดิมจนข้อมูลทุกตัวมีการเรียงลำดับขั้นตอนการทำงานของอัลกอริทึม
08 กันยายน 2552
DTS09-02-09-2552
โครงสร้างข้อมูลกราฟ
กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด
กราฟมีลักษณะเป็นเซ็ตของจุด (Point) และเซ็ตของเส้น (Line) ซึ่งแต่ละเส้นทำหน้าที่เชื่อมต่อจุดเข้าด้วยกัน แต่ละจุดเรียกว่าโหนด (Node) ของกราฟและเส้นเรียกว่าเอจ (Edge) บางครั้งเอจจะเรียกว่าอาร์ค (Arc) และโหนดเรียกว่าเวอร์ทิค (Vertice) โดยกำหนดให้กราฟ G มีเซ็ตของโหนดเป็น VG และเซ็ตของเอจเป็น EG เช่นในรูปที่ 10.1 VG ={a,b,c,d} และ EG = {1,2,3,4,5,6,7,8} จำนวนสมาชิกที่มีใน VG เรียกว่าออเดอร์ (Order) ของกราฟ ถ้าออเดอร์เท่ากับ 0 คือ กราฟไม่มีสมาชิกเรียกว่านัลกราฟ (Null Graph)
รูปที่ 10.1 ตัวอย่างกราฟที่มีจำนวนสมาชิกออเดอร์เท่ากับ 4 เอาของแต่ละโหนดจะพิจารณาจากการเชื่อมต่อกัน เช่น เอจ 4 เชื่อมโหนด c กับ d และกำหนดเป็น Path (c,d) โดยตำแหน่งของสมาชิกไม่มีความสำคัญ ดังนั้น กราฟในรูปที่ 10.1 จึงเท่ากับกราฟในรูปที่ 10.2 ต่อไปนี้
รูปที่ 10.2 ตัวอย่างกราฟที่เท่ากับกราฟในรูปที่ 10.1 โดยตำแหน่งของโหนดที่ต่างกัน ในการเชื่อมต่อกันระหว่างสองโหนดอาจมีได้หลาย ๆ เอจ เช่น เอจ 5, 6, และ 7 ซึ่งเป็น Path (b,d) ทั้งหมด เช่นกันไม่มีเอจที่เป็น Path(a,d) บางเอจเชื่อมต่อกันเพียงโหนดเดียวกับตัวเองคือเอจ 8 ที่เป็น Path(a,a) แบบวนลูป
กราฟ G จะเป็นกราฟเรียบง่าย (Simple Graph) ในรูปที่ 10.3 ต้องเป็นไปตามเงื่อนไข ดังนี้
ต้องไม่มีการวนลูปของเอจเกิดขึ้นใน EG หรือมี Path(V,V)
ต้องไม่มีเอจมากกว่าหนึ่งเชี่อมต่อกันระหว่างสองโหนด
รูปที่ 10.3 ตัวอย่างกราฟเรียบง่าย
กราฟ G ถ้าไม่ใช่กราฟเรียบง่ายเรียกว่า มัลติกราฟ (Multigraph)
กราฟ G จะเป็นกราฟต่อกัน (Connected Graph) ก็ต่อเมื่อไม่สามารถแยกออกเป็นสองกราฟ ยกเว้นมีการตัดเอจใดเอจหนึ่งออกไป ส่วนกราฟที่ไม่ต่อกันดังวนรูปที่ 10.4 มีโหนด f และ h ไม่ต่อกับโหนดอื่น
รูปที่ 10.4 ตัวอย่างกราฟที่ไม่ต่อกัน
เส้นทาง
เส้นทางในกราฟ (Path) เป็นการจัดลำดับของเอจที่มีตั้งแต่หนึ่งหรือมากกว่าทำการเชื่อมต่อระหว่างสองโหนด ซึ่งกำหนดเป็น P(Vi,Vj) คือ เส้นทางการเชื่อมระหว่างโหนด Vi กับ Vj และถ้า P(Vi,Vj) มีในกราฟก็จะต้องอยู่ใน EG ดังนั้น ลำดับของเอจจะอยู่ในรูปแบบต่อไปนี้ P(Vi,Vj) = (Vi,X1) (X1,X2) . . . (Xn-1,Xn) (Xn,Vj) และจะได้ความยาวของเส้นทางเป็นจำนวนเอจที่ประกอบรวมกัน จากกราฟเรียบง่ายในรูปที่ 10.3 จะได้เส้นทางระหว่างโหนด b กับ d ดังนี้เส้นทาง 1 P(b,d) = (b,c)(c,d) ความยาวเท่ากับ 2เส้นทาง 2 P(b,d) = (b,c)(c,b)(b,c)(c,d) ความยาวเท่ากับ 4เส้นทาง 3 P(b,d) = (b,d) ความยาวเท่ากับ 1เส้นทาง 4 P(b,d) = (b,c)(c,b)(b,d) ความยาวเท่ากับ 3 โดยทั่วไปเส้นทางที่ต้องการและสนใจเลือกใช้คือ เส้นทางที่วิ่งผ่านโหนดเพียงครั้งเดียวเท่านั้น ก็จะได้เฉพาะเส้นทาง 1 กับ 3 ส่วนเส้นทาง 2 มีการวิ่งผ่านโหนด b และ c สองครั้งและเส้นทาง 4 วิ่งผ่านโหนด b สองครั้ง นอกจากนี้ยังสนใจเฉพาะเอจที่ถูกวิ่งผ่านเพียงครั้งเดียวเช่นกัน เนื่องจากช่วยให้อัลกอริทึมไม้ต้องล่าช้าที่ต้องกลับไปทำงานในเส้นทางเดิม
DTS08-26-08-2552
โครงสร้างข้อมูลทรี
โครงสร้างข้อมูลในบทต่าง ๆ ที่ดังกล่าวผ่านมาเป็นโครงสร้างเชิงเส้น (Linear Data Structure) แต่ละสมาชิกจะมีสมาชิกตัวถัดไปเพียงตัวเดียว สำหรับในบทนี้จะกล่าวถึงโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) ซึ่งแต่ละสมาชิกสามารถมีสมาชิกตัวถัดไปได้หลายตัว โดยมีแนวความคิดของโครงสร้างแตกสาขา (Branching Structure) และเป็นที่รู้จักคือ โครงสร้างข้อมูลทรี (Tree) ซึ่งกล่าวถึงในบทนี้กับโครงสร้างข้อมูลกราฟ (Graph)
ทรีทั่วไป
จากลักษณะของทรีทั่วไป (General Tree) มีการกำหนดเป็นระดับซึ่งมีตัวแรก คือรูททรี (Rooted Tree) ซึ่งมีเพียงโหนกเดียวทำหน้าที่เป็นรูท (Root) และมีความแตกต่างจากโหนดอื่น ๆ รูทของทรี T จะกำหนดเป็น Root(T) โดยทรี T เป็นเซตจำนวนที่แน่นอน (Finite Set) ตั้งแต่ 0 หรือมากกว่าของโหนด(V1,V2,….,Vn) ดังนั้น
จะมีเพียงโหนอเดียว(V1) ที่ออกแบบเป็นพิเศษ เรียกว่า Root(T)
โหนดที่เหลือ (V2,….,Vn) จะถูกแบ่งออกเป็นส่วน ๆ เท่ากับ m≥ 0 ที่ต่อกันเป็นเซตชื่อ T1, T2,…..,Tmจะได้ว่าแต่ละ Ti คือ ทรีและเป็นทรีย่อย
หากทรีใด ๆ ไม่มีโหนดเลยเรียกว่านัลทรี (Null Tree)
รูปที่9.1 ตัวอย่างทรีทั่วไป
จากรูปที่ 9.1 เป็นตัวอย่างทรีที่แสดงแต่ละโหนด โดยใช้ตัวอักษรอยู่ภายในวงกลมและมีรูทของทรี Root(T) = A ทรีย่อยของรูท A ประกอบด้วยรูท B,C,D ซึ่งจะได้ B เป็นรูทของทรีที่มีหนึ่งทรีย่อยของรูท E ที่ไม่มีทรีย่อย ทรีที่มีรูท C จะมีสองทรีย่อยคือที่รูท F และรูท G ตามลำดับ
บางครั้งอาจมีการกำหนดลักษณะให้กับเอจ (Edge) ของทรีมีทิศทาง โดยเอจจะเริ่มจากรูทโหนดไปยังรูทของทรีย่อย ดังในรูปที่ 9.2 เป็นทรีคว่ำในลักษณะของโครงสร้างทรีที่นิยมใช้กันโดยรูทอยู่ด้านบนสุด (Top) ดังที่กล่าวมาโหนดที่ออกแบบเป็นพิเศษ คือ รูท มีความแตกต่างจากโหนดอื่น ๆ ด้วยคุณสมบัติที่ว่า In-degree(v) = 0 for v = Root(T)
รูปที่ 9.2 ตัวอย่างโครงสร้างข้อมูลทรีทั่วไปกับเอจที่มีทิศทาง โหนดที่เป็นรูทจะมีจำนวนเอจหรือกิ่งเข้ามาหรือดีกรรีเข้า (In-degree) เท่ากับ 0 เนื่องจากทรีเป็นกราฟเชื่อมกันจึงมีได้เพียงโหนดเดียวที่มีคุณสมบัตินี้ และมีทรีย่อยของ A ดังในรูปที่ 9.3 ซึ่งมีเอจเชื่อมจาก A ไม่ใช่โหนดในทรีเหล่านี้
รูปที่ 9.3 ทรีย่อยของทรีในรูปที่ 9.2
ทรีทั่วไปที่กล่าวถึงมีความหมายเช่นเดียวกับต้นไม้มที่มีการสืบทอด ดังนั้น ถ้ามี Edge(A,B) จะได้ว่า A เป็นโหนดพ่อ (Parent Node) ของ BและB เป็นโหนดลูก (Child Node)ของAแต่ละโหนดที่เป็นลูกจะมีโหนดพ่อเพียงโหนดเดียว สองโหนดขึ้นไปที่มีโหนดพ่อเดียวกันเรียกว่าโหนดพี่น้อง (Sibling Node) สำหรับโหนดที่มีจำนวนเอสชี้ออกไปหรือดีกรีออกเป็นโหนดที่ไม่มีโหนดลูก
ไบนารี่ทรี
ประเภทของทรีทั่วไปที่มีความสำคัญมากที่สุด คือ ไบนารี่ทรี (Binary Tree) เป็นเซตของโหนดที่มีจำนวนแน่นอนซึ่งอาจจะว่างเปล่าหรือเชื่อมต่อกับสองไบนารี่ทรีที่เรียกว่าทรีย่อยซ้าย (Left Subtree) และบททรีย่อยขวา (Right Subtree) โดยมีข้อกำหนดว่าดีกรีออกมากที่สุดเท่ากับ 2 ซึ่งกำหนดให้เป็นทรีย่อยด้านซ้ายและขวา จากรูปที่ 9.4 (a) และ (b) เป็นไบนารี่ทรีที่แตกต่างกันเนื่องจาก รูป (a) มีทรีย่อยซ้าย ส่วน (b) ไม่เป็นไบนารี่ทรีเนื่องจากมีทรีย่อยไม่ช่ด้านซ้ายหรือขวาแต่ชี้ตรงลงมา
(a) ทรี 1 (b) ทรี 2 (c) ทรี 3 รูปที่ 9.4 ตัวอย่างทรีที่เป็นไบนารี่ทรี (a),(b) ลัไม่ใช่ (c)
ไบนารี่ที่มีคุณสมบัติที่แตกต่างจากทรีทั่วไป เมื่อพิจารราไบนารี่ทรีที่มี K ระดับในรูปที่ 9.5 จะเรียกว่าไบนารี่ทรีสมบูรณ์ (Complete Binary Tree) ซึ่งจะมีจำนวนโหนดมากที่สุดที่เป็นไปได้ตามความสูงของไบนารี่ทรี จำนวนเอจก็จะเพิ่มเป็นสองเท่าของระดับก่อนหน้ายกเว้นระดับ 0 และจำนวนโหนดมากที่สุดในระดับ I จะได้ว่าไบนารี่ทรีสมบูรณ์ที่มี k ระดับ จะมีโหนดทั้งหมดเท่ากับ 2k-1 เช่น ไบนารี่ทรีสมบูรณ์ที่มี 3 ระดับจะมี 7 โหนด ถ้ามี 10 ระดับ จะมี 1023 โหนด
