DTS11-15/09/2009

Sorting

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

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

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

DTS10-08/09/2009

Sorting



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



-การจัดเรียงภายใน (internal sorting) การจัดเรียงแบบนี้ ข้อมูลที่จะถูกจัดเรียงต้องเก็บ หรือใช้
หน่วยความจำของเครื่องคอมพิวเตอร์ (RAM) เป็นหลักในการประมวลผลโดยใช้โครงสร้างข้อมูล เช่น อาร์เรย์หรือลิงก์ลิสต์ร่วมด้วย
-การจัดเรียงภายนอก (external sorting) กรณีที่ข้อมูลจำนวนมากไม่สามารถนำไปเก็บไว้ในหน่วยความจำ (RAM) เพื่อประมวลผลได้ทั้งหมด (พึงระลึกไว้ว่า CPU ไม่สามารถประมวลผลกับสื่อข้อมูลที่
เป็นดิสก์ได้) ดังนั้นการจัดเรียงจะทำการจัดเรียงภายนอก โดยใช้วิธีแบ่งข้อมูลออกเป็นส่วนย่อย ซึ่งบางส่วนจะคงไว้ในดิสก์ และทยอยนำข้อมูลบางส่วนเข้าสู่หน่วยความจำ (RAM) เพื่อทำการจัดเรียง



1. การเรียงลำดับแบบเลือก (Selection Sort)
เป็นวิธีที่ง่ายที่สุดในการเรียงลำดับข้อมูล โดยเริ่มจาก
- หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดแล้วสลับค่าของตำแหน่งข้อมูลนั้นกับค่าข้อมูลในตำแหน่ง A(1) จะได้ A(1) มีค่าน้อยที่สุด
- หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดในกลุ่ม A(2), A(3),....,A(n) แล้วทำกับสลับค่าข้อมูลในตำแหน่ง A(2) อย่างนี้เรื่อยไปจน กระทั่งไม่เกิน N-1 รอบ ก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมาก


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

DTS09-01/09/2009

กราฟ (Graph)

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

และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง(Directed Graphs)บางครั้งเรียกว่า ไดกราฟ (Digraph)

การเขียนกราฟเพื่อแสดงให้เห็นความสัมพันธ์ ของสิ่งที่เราสนใจแทนโหนดด้วย จุด (pointes) หรือวงกลม (circles)

การแทนกราฟในหน่วยความจำ

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