เรื่อง Sorting

การเรียงลำดับ (Sorting)

การเรียงลำดับ - เป็นการจัดให้เป็นระเบียบมีแบบแผน

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

การเรียงลำดับอย่างมีประสิทธิภาพ

หลักเกณฑ์ในการพิจารณาเพื่อเลือกวิธีการเรียงลำดับ
ที่ดีและเหมาะสมกับระบบงานเพื่อให้ประสิทธิภาพใน
การทำงานสูงสุดควรจะต้องคำนึงถึงสิ่งต่างๆดังต่อไปนี้

(1) เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม
(2) เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตาม
โปรแกรมที่เขียน
(3) จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่

วิธีการเรียงลำดับ

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


(1)การเรียงลำดับแบบภายใน (internal sorting)

เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำ
หลักเวลาที่ใช้ในการเรียงลำดับจะคำนึงถึงเวลาที่ใช้ในการ
เปรียบเทียบและเลื่อนข้อมูลภายในความจำหลัก

(2) การเรียงลำดับแบบภายนอก(external sorting)

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

การเรียงลำดับแบบเลือก (selection sort)

ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ข้อมูลนั้นควรจะอยู่ทีละ
ตัวโดยทำการค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับถ้าเป็น
การเรียงลำดับจากน้อยไปมาก

1. ในรอบแรกจะทำการค้นหาข้อมูล
ตัวที่มีค่าน้อยที่สุดมาเก็บไว้ที่ตำแหน่งที่ 1
2. ในรอบที่สองนำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บไว้ที่
ตำแหน่งที่สอง
3. ทำเช่นนี้ไปเรื่อยๆจนกระทั่งครบทุกค่าในที่สุดจะได้ข้อมูล
เรียงลำดับจากน้อยไปมากตามที่ต้องการ




การเรียงลำดับแบบฟอง (Bubble Sort)

เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลใน
ตำแหน่งที่อยู่ติดกัน1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับ
ที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน2. ถ้าเป็นการเรียง
ลำดับจากน้อยไปมากให้นำข้อมูลตัวที่มีค่าน้อยกว่าอยู่
ในตำแหน่งก่อนข้อมูลที่มีค่ามากถ้าเป็นการเรียงลำดับ
จากมากไปน้อยให้นำข้อมูลตัวที่มีค่ามากกว่าอยู่ใน
ตำแหน่งก่อนข้อมูลที่มีค่าน้อย

การจัดเรียงลำดับแบบฟองเป็นวิธีที่ไม่ซับซ้อนมากนัก

เป็นวิธีการเรียงลำดับที่นิยมใช้กันมากเพราะมีรูปแบบที่

เข้าใจง่ายแต่ประสิทธิภาพการทำงานค่อนข้างต่ำพอๆ

กับการเรียงลำดับแบบเลือกในหัวข้อที่ผ่านมาถ้ามีจำนวน

ข้อมูลทั้งหมด n ตัวไม่ว่าข้อมูลจะเป็นอย่างไรก็ตามต้อง

ทำการเปรียบเทียบทั้งหมด n .1 รอบและจำนวนครั้งของ

การเปรียบเทียบในแต่ละรอบเป็นดังนี้

การเรียงลำดับแบบเร็ว (quick sort)

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


การเรียงลำดับแบบแทรก (insertion sort)

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





การเรียงลำดับแบบฐาน (radix sort)

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






DTS : 10-13-08-2552