DTS08-09-09-2552

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

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

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

การเรียงลำดับแบบเร็วการเรียงลำดับแบบเร็ว (quick sort)
เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็วในการทำงาน วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูลขึ้นมาหนึ่งค่าเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูกต้องแล้วใช้ค่าหลักนี้เป็นหลักในการแบ่งข้อมูลออกเป็น สองส่วน ถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่ในตอนหน้าข้อมูลทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่งส่วน และอีกส่วนหนึ่งจะอยู่ในตำแหน่งตอนหลังข้อมูลทั้งหมดจะมีค่ามากกว่าค่าหลัก แล้วนำแต่ละส่วนย่อยไปแบ่งย่อยในลักษณะเดียวกันต่อไป จนกระทั่งแต่ละส่วนไม่สามารถแบ่งย่อยได้อีกต่อไปจะได้ข้อมูลที่มีการเรียงลำดับตามที่ต้องการ

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

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

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

DTS08-02-09-2552

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

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

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

การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal)คือกระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียวแต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทางการท่องไปในกราฟมี 2 แบบดังนี้
- การท่องแบบกว้าง (Breadth First Traversal)วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ
- การท่องแบบลึก (Depth First Traversal)การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้นย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด

DTS08-26-08-2552

Tree

ทรี หรือโครงสร้างข้อมูลแบบต้นไม้ ประกอบด้วยโหนด (node) ซึ่งเป็นส่วนที่เก็บข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings) โหนดที่ไม่มีโหนดลูกเรียกว่า โหนดใบ (Leave Node) เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดเรียกว่า กิ่ง (Beanch) คือ โหนดที่ไม่ใช่ Leaf Node
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใดๆ ในทรีต้องมีทางติดต่อกัน ทางเดียวกันนั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N -1เส้น
การเขียนรูปแบบทรี อาจเขียนได้ 4 แบบ คือ
1. แบบที่มีรากอยู่ด้านบน
2. แบบที่มีรากอยู่ด้านล่าง
3. แบบที่มีรากอยู่ด้านซ้าย
4. แบบที่มีรากอยู่ด้านขวาการท่องไปในไบนารีทรี (Traversing Binary Tree)คือ การเข้าไปเยือนทุก ๆ โหนดในทรี วิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้ง วิธีการท่องไปนั้นมีด้วยกันหลายแบบ โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)ทรีย่อยทางซ้าย (แทนด้วย L) หรือทรีย่อยทางขวา (แทนด้วย R)วิธีการท่องเข้าไปในทรีมี 6 วิธีคือ NLR LNR LRN NRL RNL และ RLN แต่วิธีการท่องเข้าไปในทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรก คือ NLRLNR LRN ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ (Recursive)ขั้นตอนวิธีดึงโหนดออกอาจแยกพิจารณาได้ 3 กรณีดังต่อไปนี้1. กรณีโหนดที่จะดึงออกเป็นโหนดใบ2. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยทางซ้ายหรือทรีย่อยทางขวาเพียงด้านใดด้านหนึ่ง3. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้ายและทรีย่อยทางขวา - ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรีย่อยทางซ้าย ต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อยทางซ้ายนั้น - ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมาจากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อยทางขวานั้น