สรุปบทเรียน การเรียงลำดับ
การเรียงลำดับข้อมูลเป็นเรื่องสำคัญมากเรื่องหนึ่งเนื่องจากทำให้ผู้ต้องการใช้ข้อมุลเช่น ผู้บริหาร,ผู้ปฏิบัติงาน (พนักงาน) สามารถทำความเข้าใจกับข้อมูลหรือทำการค้นหาข้อมูลได้ง่ายและเร็วยิ่งขึ้นตามที่ต้องการ
การเรียงลำดับที่ดี และเหมาะสมกับระบบงาน เพื่อให้ประสิทธิภาพในการ
ทำงานสูงสุด ควรจะต้องคำนึงถึงสิ่งต่าง ๆ ดังต่อไปนี้
(1) เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม
(2) เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตามโปรแกรมที่เขียน
(3) จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่
วิธีการเรียงลำดับ
วิธีการเรียงลำดับสามารถแบ่งออกเป็น2 ประเภท คือ
(1)การเรียงลำดับแบบภายใน (internal sorting)เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ใน
หน่วยความจำหลัก เวลาที่ใช้ในการเรียงลำดับจะคำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อนข้อมูลภายในความจำหลัก
(2) การเรียงลำดับแบบภายนอก
(external sorting) เป็นการเรียงลำดับข้อมูลที่
เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการ
เรียงลำดับข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ใน
การเรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่าง
การถ่ายเทข้อมูลจากหน่วยความจำหลักและ
หน่วยความจำสำรองนอกเหนือจากเวลาที่ใช้
ในการเรียงลำดับข้อมูลแบบภายใน
การเรียงลำดับแบบเลือก (selection sort)ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ทีละ
ตัว โดยทำการค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับ
ถ้าเป็นการเรียงลำดับจากน้อยไปมาก
1. ในรอบแรกจะทำการค้นหาข้อมูลตัวที่มีค่าน้อยที่สุดมาเก็บ
ไว้ที่ตำแหน่งที่ 1
2. ในรอบที่สองนำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บไว้ที่
ตำแหน่งที่สอง
3. ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกค่า
ในที่สุดจะได้ข้อมูลเรียงลำดับจากน้อยไปมากตามที่ต้องการ
การจัดเรียงลำดับแบบเลือกเป็นวิธีที่ง่ายและ
ตรงไปตรงมา แต่มีข้อเสียตรงที่ใช้เวลาในการจัดเรียงนาน
เพราะแต่ละรอบต้องเปรียบเทียบกับข้อมูลทุกตัว ถ้ามี
จำนวนข้อมูลทั้งหมด n ตัว ต้องทำการเปรียบเทียบทั้งหมด
n – 1 รอบ และจำนวนครั้งของการเปรียบเทียบในแต่ละ
รอบเป็นดังนี้
รอบที่ 1 เปรียบเทียบเท่ากับ n −1 ครั้ง
รอบที่ 2 เปรียบเทียบเท่ากับ n – 2 ครั้ง
...
รอบที่ n – 1 เปรียบเทียบเท่ากับ 1 ครั้ง
การเรียงลำดับแบบฟอง (Bubble Sort)
เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลใน
ตำแหน่งที่อยู่ติดกัน
1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่ง
ที่อยู่กัน
2. ถ้าเป็นการเรียงลำดับจากน้อยไปมากให้นำข้อมูลตัวที่มี
ค่าน้อยกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก ถ้า
เป็นการเรียงลำดับจากมากไปน้อยให้นำข้อมูล ตัวที่มี
ค่ามากกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่าน้อย
ในวิธีแบบ Bubble Sort ค่าในการเปรียบเทียบที่น้อยที่สุดหรือมากที่สุด จะลอยขึ้นข้างบน เหมือนกับฟองอากาศ
การเรียงลำดับอย่างเร็ว (quick sort)จะแบ่งข้อมูลเป็นสองกลุ่ม โดยใน การจัดเรียงจะเลือกข้อมุลตัวใดตัวหนึ่งออกมา ซึ่งจะเป็นตัวที่แบ่งข้อมูลออกเป็นสองกลุ่ม โดยกลุ่มแรกจะต้องมีข้อมูลน้อยกว่า ตัวแบ่ง และกลุ่มที่มีข้อมูลน้อยกว่าตัวแบ่ง และอีกกลุ่มจะมีข้อมูลที่มากกว่าตัวแบ่ง ซึ่งเราเรียกตัวแบ่งว่า ตัวหลัก(pivot) ในการเลือกตัวหลักจะมีอิสระในการเลือกข้อมูลตัวใดก็ได้ที่เราต้องการ การเรียงลำดับแบบเร็วเหมาะกับข้อมูลที่มีการเรียกซ้ำ
การเรียงลำดับแบบแทรก (insertion sort)เป็นการเรียงลำดับที่เพิ่มสมาชิกใหม่เข้าไปในเซ็ต ที่มีการเรียงลำดับข้อมูลอยู่แล้ว แล้วทำให้เซ็ตใหม่มีการเรียงลำดับด้วย
1. เริ่มเปรียบเทียบข้อมูลตำแหน่งที่ 1 และ 2 หรือข้อมูลตำแหน่งสุดท้ายกับรองสุดท้าย
2. ถ้าเป็นการเรียงข้อมูลจากค่าน้อยไปมาก จัดเรียงข้อมูลที่มีค่าน้อยอยู่ก่อนข้อมูลที่มีค่ามาก ถ้าเป็นการเรียงข้อมูลจากมากไปน้อย จัดเรียงข้อมูลที่มีค่ามากอยู่ก่อนข้อมูลที่มีค่าน้อย
ป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละ
หลัก
1. เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน นั่นคือถ้า
ข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่วยก่อน
2. การจัดเรียงจะนำข้อมูลเข้ามาทีละตัว แล้วนำไป
เก็บไว้ที่ซึ่งจัดไว้สำหรับค่านั้น เป็นกลุ่ม ๆ
ตามลำดับการเข้ามา
3. ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้
รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน โดยเริ่มเรียง
จากกลุ่มที่มีค่าน้อยที่สุดก่อนแล้วเรียงไปเรื่อย ๆ จน
หมดทุกกลุ่ม
4. ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลัก
หน่วยเรียบร้อยแล้วมาพิจารณาจัดเรียงในหลักสิบ
ต่อไป ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกหลักจะ
ได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามต้องการ
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น