ความรู้ที่ได้รับจากเรื่อง Sorting
การเรียงลำดับ (sorting) เป็นการจัดให้เป็นระเบียบ มีแบบแผน ช่วยในการค้นหาข้อมูลได้อย่างรวดเร็วและมีประสิทธิภาพ
สิ่งที่ควรคำนึงถึง
1. เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม
2. เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตามโปรแกรมที่เขียน
3. จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่
วิธีการเรียงลำดับ
1. การเรียงลำดับแบบภายใน (internal sorting) = เรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก
2. การเรียงลำดับแบบภายนอก (external sorting) = เรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง
การเรียงลำดับแบบเลือก (selection sort)
1. รอบแรก ทำการค้นหาข้อมูลตัวที่มีค่าน้อยที่สุดมาเก็บไว้ที่ตำแหน่งที่ 1
2. รอบที่สอง นำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บไว้ที่ตำแหน่งที่ 2
3. ทำไปเรื่อยๆจนครบทุกค่าและจะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามที่ต้องการ
ข้อดี = ง่ายและตรงไปตรงมา
ข้อเสีย = ใช้เวลาในการจัดเรียงนาน
การเรียงลำดับแบบฟอง (Bubble Sort)
ใช้เปรียบเทียบข้อมูลในตำแหน่งที่อยู่ติดกัน จะเริ่มจากคู่แรกหรือคู่สุดท้ายก่อนก็ได้ วิธีนี้เป็นที่นิยมมากเพราะมีรูปแบบที่เข้าใจง่าย แต่ประสิทธิภาพค่อนข้างต่ำพอๆ กับการเรียงลำดับแบบเลือก
1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน
2. ถ้าเป็นการเรียงลำดับจากน้อยไปมาก ให้นำข้อมูลตัวที่น้อยกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มาก
แต่ถ้าเป็นการเรียงลำดับจากมากไปน้อยให้นำข้อมูล ตัวที่มากกว่าอยู่ในตำแหน่งก่อนข้อมูลที่น้อย
จำนวนครั้งของการเปรียบเทียบ มี 2 กรณี ดังนี้
1. กรณีที่ดีที่สุด (Best Case) = จะเปรียบเทียบในรอบแรกรอบเดียวเท่านั้น
2. กรณีที่แย่ที่สุด (Worst Case) = n(n-1)/2 ครั้ง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น