สรุปเนื้อหาบทเรียน "Data Structure" เรื่อง Graph (ต่อ) และ Sorting
การท่องไปในกราฟ (graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้นเพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำเครื่องหมายมาร์คบิตบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้วเพื่อไม่ให้เข้าไปเยือนอีก
สำหรับเทคนิคการท่องไปในกราฟมี 2 แบบดังนี้
การท่องแบบกว้าง (Breadth first traversal) วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับ จนกระทั่งเยือนหมดทุกโหนดในกราฟ
การท่องแบบลึก (Depth first traversal) การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด Sorting
การเรียงลำดับข้อมูลเป็นเรื่องสำคัญมากเรื่องหนึ่งเนื่องจากทำให้ผู้ต้องการใช้ข้อมุลเช่น ผู้บริหาร,ผู้ปฏิบัติงาน (พนักงาน) สามารถทำความเข้าใจกับข้อมูลหรือทำการค้นหาข้อมูลได้ง่ายและเร็วยิ่งขึ้นตามที่ต้องการ
การเรียงข้อมูล สามารถแบ่งได้เป็น 2 ประเภทด้วยกันคือ
การเรียงข้อมูลแบบภายใน (Internal Sorting) คือ การเรียงลำดับข้อมูล โดยทั้งหมดต้องจัดเก็บอยู่ในหน่วยความจำหลัก (main memory) ที่มีการเข้าถึงข้อมูลได้เร็ว โดยไม่จำเป็นต้องใช้หน่วยความจำสำรอง เช่น ดิสค์ หรือเทปสำหรับการจัดเก็บชั่วคราว ใช้ในกรณีที่ข้อมูลไม่มากเกินกว่าพื้นที่ความจำที่กำหนดให้กับผู้ใช้แต่ละราย
การเรียงข้อมูลแบบภายนอก (External Sorting) คือ การ เรียงลำดับข้อมูลที่มีขนาดใหญ่เกินกว่าที่จะสามารถเก็บไว้ใน พื้นที่ความจำหลักที่กำหนดให้ได้ในคราวเดียว ดังนั้นข้อมูล ส่วนมากต้องเก็บไว้ในไฟล์ข้อมูลที่อยู่บนดิสค์ เทป เป็นต้น สำหรับการเรียงข้อมูลแบบภายนอกจะต้องคิดถึงเวลาที่ใช้ใน การถ่ายเทข้อมูลจากหน่วยความจำชั่วคราวกับหน่วยความจำหลัก ด้วยเช่นกัน
การเรียงลำดับแบบเลือก (Selection Sort) เป็นวิธีที่ง่ายที่สุดในการเรียงลำดับข้อมูล โดยเริ่มจาก - หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดแล้วสลับค่าของตำแหน่งข้อมูลนั้นกับค่าข้อมูลในตำแหน่ง A(1) จะได้ A(1) มีค่าน้อยที่สุด - หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดในกลุ่ม A(2), A(3),....,A(n) แล้วทำกับสลับค่าข้อมูลในตำแหน่ง A(2) อย่างนี้เรื่อยไปจน กระทั่งไม่เกิน N-1 รอบ ก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมาก
การเรียงลำดับแบบแทรก (Insertion Sort) หลักการ คือ
1. อ่านข้อมุลที่ต้องการเรียงลำดับเข้ามาทีละตัวโดยเริ่มจากตัวแรกก่อน และหาตำแหน่งของข้อมูลที่ควรจะอยู่
2. หาที่ว่างสำหรับข้อ 1.
3. Insert หรือแทรกข้อมูล ณ ตำแหน่งในข้อ 2.
การเรียงลำดับแบบบับเบิล (Bubble Sort) วิธัการเรียงลำดับแบบบับเบิลจะทำการเปรียบเทียบข้อมูลที่อยู่ในตำแหน่งที่ติดกัน ถ้าข้อมูลไม่อยู่ใลำดับที่ถูกต้อง ก็จะทำการสลับตำแหน่งของข้อมูลที่เปรียบเทียบโดยที่การเปรียบเทียบจะเริ่มที่ตำแหน่งที่ 1 กับตำแหน่งที่ 2 ก่อน ต่อไปนี้เทียบกับ ตำแหน่งที่ 2 และตำแหน่งที่ 3 จนถึงตำแหน่งที่จัดเรียงแล้ว จากนั้นจะกลับไปเริ่มต้นการเปรียบเทียบอีกจนกระทั่งจัดเรียง เรียบร้อยหมดทุกตำแหน่ง ในวิธีแบบ Bubble Sort ค่าในการเปรียบเทียบที่น้อยที่สุดหรือมากที่สุด จะลอยขึ้นข้างบน เหมือนกับฟองอากาศ
การเรียงลำดับโดยการใช้ฐานเลข(radix sort) การเรียงลำดับแบบนี้การเรียงลำดับ จะอยู่บนพื้นฐานของการแทนตำแหน่งของตัวเลขที่ต้องการนำมาเรียงลำดับ จะเริ่มจากตัวที่มีเลขนัยสำคัญสูงที่สุด ดำเนินจนกระทั่งถึงตัวเลขที่มีเลขนัยสำคัญต่ำสุด การเรียงลำดับในวิธีนี้การเรียงลำดับ จะเรียงจากตัวเลขที่มีนัยสำคัญน้อยที่สุดก่อน เมื่อตัวเลขทั้งหมดถูกนำมาเรียงลำดับตามเลขนัยสำคัญที่สูงขึ้น ตัวเลขที่เหมือนกัน ในตำแหน่งน้น จะต่างกันในตำแหน่งของเลขนัยสำคัญที่น้อยกว่า การประมวลผลแบบนี้จะประมวลผลกับข้อมูลทั้งหมดได้ โดยที่ไม่ต้องมีการแบ่งข้อมูลแบบกลุ่มย่อย
การเรียงลำดับอย่างเร็ว(quick sort) จะแบ่งข้อมูลเป็นสองกลุ่ม โดยใน การจัดเรียงจะเลือกข้อมุลตัวใดตัวหนึ่งออกมา ซึ่งจะเป็นตัวที่แบ่งข้อมูลออกเป็นสองกลุ่ม โดยกลุ่มแรกจะต้องมีข้อมูลน้อยกว่า ตัวแบ่ง และกลุ่มที่มีข้อมูลน้อยกว่าตัวแบ่ง และอีกกลุ่มจะมีข้อมูลที่มากกว่าตัวแบ่ง ซึ่งเราเรียกตัวแบ่งว่า ตัวหลัก(pivot) ในการเลือกตัวหลักจะมีอิสระในการเลือกข้อมูลตัวใดก็ได้ที่เราต้องการ การเรียงลำดับแบบเร็วเหมาะกับข้อมูลที่มีการเรียกซ้ำ
ไม่มีความคิดเห็น:
แสดงความคิดเห็น