DTS : 10-09/09/2552

Sorting

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

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

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

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

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

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

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