มีแบบแผน ช่วยให้การค้นหาสิ่งของหรือข้อมูล ซึ่งจะสามารถ
กระทำได้รวดเร็วและมีประสิทธิภาพ เช่น การค้นหา
ความหมายของคำในพจนานุกรม ทำได้ค่อนข้างง่ายและ
รวดเร็วเนื่องจากมีการเรียงลำดับคำตามตัวอักษรไว้อย่างมี
ระบบและเป็นระเบียบ หรือ การค้นหาหมายเลขโทรศัพท์ใน
สมุดโทรศัพท์ ซึ่งมีการเรียงลำดับ ตามชื่อและชื่อสกุลของ
เจ้าของโทรศัพท์ไว้ ทำให้สามารถค้นหา หมายเลข
โทรศัพท์ของคนที่ต้องการได้อย่างรวดเร็ว
การเรียงลำดับอย่างมีประสิทธิภาพ
หลักเกณฑ์ในการพิจารณาเพื่อเลือกวิธีการเรียงลำดับที่
ดี และเหมาะสมกับระบบงาน เพื่อให้ประสิทธิภาพในการ
ทำงานสูงสุด ควรจะต้องคำนึงถึงสิ่งต่าง ๆ ดังต่อไปนี้
(1) เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม
(2) เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตาม
โปรแกรมที่เขียน
(3) จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอ
หรือไม่
วิธีการเรียงลำดับ
เนื่องจากมีวิธีการมากมายที่สามารถใช้ในการเรียงลำดับ
ข้อมูลได้ บางวิธีก็มีขั้นตอนการจัดเรียงเป็นแบบง่าย ๆ ตรงไป
ตรงมา แต่ใช้เวลาในการจัดเรียงลำดับนาน และบางวิธีก็มี
ขั้นตอนในการจัดเรียงลำดับแบบซับซ้อนยุ่งยากแต่ใช้เวลา
ในการจัดเรียงไม่นานนัก ดังนั้นจึงควรศึกษาวิธีการจัดเรียง
ลำดับด้วยวิธีการต่าง ๆ เพื่อเลือกใช้วิธีการที่ดีและเหมาะสม
กับระบบงานนั้นที่สุด วิธีการเรียงลำดับสามารถแบ่งออกเป็น
2 ประเภท คือ
(1)การเรียงลำดับแบบภายใน (internal sorting)
เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ใน
หน่วยความจำหลัก เวลาที่ใช้ในการเรียงลำดับจะ
คำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อน
ข้อมูลภายในความจำหลัก
(2) การเรียงลำดับแบบภายนอก
(external sorting) เป็นการเรียงลำดับข้อมูลที่
เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการ
เรียงลำดับข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ใน
การเรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่าง
การถ่ายเทข้อมูลจากหน่วยความจำหลักและ
หน่วยความจำสำรองนอกเหนือจากเวลาที่ใช้
ในการเรียงลำดับข้อมูลแบบภายใน
การเรียงลำดับแบบเลือก (selection sort)
ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ทีละ
ตัว โดยทำการค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับ
ถ้าเป็นการเรียงลำดับจากน้อยไปมาก
1. ในรอบแรกจะทำการค้นหาข้อมูลตัวที่มีค่าน้อยที่สุดมาเก็บ
ไว้ที่ตำแหน่งที่ 1
2. ในรอบที่สองนำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บไว้ที่
ตำแหน่งที่สอง
3. ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกค่า
ในที่สุดจะได้ข้อมูลเรียงลำดับจากน้อยไปมากตามที่ต้องการ
ในรอบที่ 1 ทำการเปรียบเทียบข้อมูลเพื่อค้นหาข้อมูลที่มีค่า
น้อยที่สุด คือ 22
นำไปวางที่ตำแหน่งที่ 1 สลับตำแหน่งกับ 35
ในรอบที่ 2 ทำการเปรียบเทียบอีกเพื่อค้นหาค่าที่น้อยที่สุด
รองลงมาโดยเริ่มค้นตั้งแต่ตำแหน่งที่ 2 เป็นต้นไปได้ค่าน้อย
ที่สุดคือ 35
นำไปวางที่ตำแหน่งที่ 2 สลับตำแหน่งกับ 67
ในรอบต่อไปก็ทำในทำนองเดียวกันจนกระทั่งถึงรอบ
สุดท้ายคือรอบที่ 7 จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมาก
ตามที่ต้องการ
การเรียงลำดับแบบฟอง (Bubble Sort)
เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลใน
ตำแหน่งที่อยู่ติดกัน
1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่ง
ที่อยู่กัน
2. ถ้าเป็นการเรียงลำดับจากน้อยไปมากให้นำข้อมูลตัวที่มี
ค่าน้อยกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก ถ้า
เป็นการเรียงลำดับจากมากไปน้อยให้นำข้อมูล ตัวที่มี
ค่ามากกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่าน้อย
จากตัวอย่าง การเปรียบเทียบจะเริ่มเปรียบเทียบ
จากคู่หลัง ในรอบที่ 1 เปรียบเทียบข้อมูลที่
ตำแหน่งที่ 7 กับ 8 ได้ว่า 43 น้อยกว่า 82 ให้
ทำการสลับตำแหน่งกันเพื่อให้ค่าที่น้อยกว่าอยู่ก่อน
ต่อไปเปรียบเทียบข้อมูลตำแหน่งที่ 6 กับ 7 ได้ว่า
43 น้อยกว่า 99 ให้ทำการสลับตำแหน่งกันอีก ทำ
การเปรียบเทียบเช่นนี้ในคู่ต่อไปเรื่อย ๆ จนกระทั่ง
ได้ค่าต่ำสุดอยู่ในตำแหน่งที่ 1
ในรอบที่ 2 ทำการเปรียบเทียบข้อมูลจากคู่หลังมา
คู่หน้าเช่นกัน แต่จะเปรียบเทียบถึงตำแหน่งที่ 2
เท่านั้นจนกระทั่งได้ค่าต่ำสุดรองลงมาไว้ในตำแหน่ง
ที่ 2 ในรอบต่อไปก็ทำในทำนองเดียวกันจนกระทั่ง
ถึงรอบสุดท้ายคือรอบที่ 7 จะเหลือข้อมูลที่ต้อง
เปรียบเทียบคู่เดียวคือข้อมูลในตำแหน่งที่ 7 กับ 8
เมื่อการจัดเรียงเสร็จเรียบร้อยเราจะได้ข้อมูลที่มีการ
เรียงลำดับจากน้อยไปมากตามที่ต้องการ
การเรียงลำดับแบบเร็ว เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะ
สำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็ว
ในการทำงาน วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูล
ขึ้นมาหนึ่งค่าเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้อง
ให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูกต้องแล้ว ใช้
ค่าหลักนี้เป็นหลักในการแบ่งข้อมูลออกเป็นสองส่วน
ถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่
ในตอนหน้าข้อมูล ทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่
เป็นตัวแบ่งส่วนอีกส่วนหนึ่งจะอยู่ในตำแหน่งตอนหลังข้อมูล
ทั้งหมด จะมีค่ามากกว่าค่าหลัก แล้วนำแต่ละ
ส่วนย่อยไปแบ่งย่อยในลักษณะเดียวกันต่อไป
จนกระทั่งแต่ละส่วนไม่สามารถแบ่งย่อยได้อีก
ต่อไปจะได้ข้อมูลที่มีการเรียงลำดับตามที่
ต้องการ
จากการเปรียบเทียบข้างต้นในที่สุดก็ได้
ตำแหน่งที่วางค่าหลัก 44 ซึ่งข้อมูลจะถูก
แบ่งเป็น 2 ส่วน ส่วนที่ 1 ข้อมูลทั้งหมดมีค่า
น้อยกว่าค่าหลัก และส่วนที่ 2 ข้อมูลทั้งหมดมี
ค่ามากกว่าค่าหลัก นำแต่ละส่วนไป
ดำเนินการเปรียบเทียบในลักษณะเดียวกัน
จนกระทั่งข้อมูลทั้งหมดเรียงลำดับจากน้อยไป
มากตามต้องการ
การเรียงลำดับแบบแทรก (insertion sort)
เป็นวิธีการเรียงลำดับที่ทำการเพิ่มสมาชิกใหม่เข้าไปใน
เซต ที่มีสมาชิกทุกตัวเรียงลำดับอยู่แล้ว และทำให้เซตใหม่
ที่ได้นี้มีสมาชิกทุกตัวเรียงลำดับด้วย วิธีการเรียงลำดับจะ
1. เริ่มต้นเปรียบเทียบจากข้อมูลในตำแหน่งที่ 1 กับ 2
หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้ายก็ได้
ถ้าเป็นการเรียงลำดับจากน้อยไปมาก
2. จะต้องจัดให้ข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งก่อน
ข้อมูลที่มีค่ามาก และถ้าเรียงจากมากไปน้อยจะก็จะ
จัดให้ข้อมูลที่มีค่ามากอยู่ในตำแหน่งก่อน
เช่น ต้องการเรียงลำดับข้อมูลจากน้อยไปมาก และ
เริ่มต้นนำข้อมูล 2 ตัวแรกมาเปรียบเทียบ ให้ข้อมูลที่มีค่า
น้อยกว่าอยู่ในตำแหน่งแรก จะได้ข้อมูลในเซตที่เรียงลำดับ
แล้วมีสมาชิก 2 ตัว จากนั้นนำสมาชิกใหม่เข้ามาโดยเริ่ม
เปรียบเทียบกับสมาชิกในเซตทีละตัว จะเริ่มเปรียบเทียบ
ตั้งแต่ตัวแรกหรือตัวหลังสุดก็ได้ ถ้าเปรียบเทียบตั้งแต่ตัว
แรกจะต้องหาตำแหน่งสมาชิกที่มีค่ามากกว่าสมาชิกใหม่
แล้วทำการถอยทุกค่าไปหนึ่งตำแหน่งตั้งแต่ตำแหน่งนั้นเป็น
ต้นไป เพื่อให้เกิดตำแหน่งว่างสำหรับแทรกสมาชิกใหม่ลง
ไปก็จะได้เซตที่เรียงลำดับใหม่
ข้อมูลเริ่มต้น
ถ้ามีจำนวนข้อมูลเป็น n การจัดเรียงแบบแทรกจะมี
การจัดเรียงทั้งหมดเท่ากับ n − 1 รอบ จำนวนครั้ง
ของการเปรียบเทียบในแต่ละรอบแตกต่างกันขึ้นอยู่กับ
ลักษณะการจัดเรียงของข้อมูลนั้น
กรณีที่ดีที่สุด คือ กรณีข้อมูลทั้งหมดจัดเรียงใน
ตำแหน่งที่ต้องการเรียบร้อยแล้ว กรณีนี้ในแต่ละรอบ
มีการเปรียบเทียบเพียงครั้งเดียว เพราะฉะนั้นจำนวน
ครั้งของการเปรียบเทียบเป็นดังนี้
จำนวนครั้งของการเปรียบเทียบ = n − 1 ครั้ง
กรณีที่แย่ที่สุด คือ กรณีที่ข้อมูลมีการเรียงลำดับในตำแหน่ง
ที่กลับกัน เช่น ต้องการเรียงลำดับจากน้อยไปมาก แต่
ข้อมูลมีค่าเรียงลำดับจากมากไปน้อย จำนวนครั้งของการ
เปรียบเทียบในแต่ละรอบดังนี้
ในรอบที่ 1 จำนวนครั้งของการเปรียบเทียบเป็น 1 ครั้ง
ในรอบที่ 2 จำนวนครั้งของการเปรียบเทียบเป็น 2 ครั้ง
จำนวนครั้งของการเปรียบเทียบ
= 1 + 2 + 3 + . . . +(n −2) + (n −1)
= n (n −1) / 2
ไม่มีความคิดเห็น:
แสดงความคิดเห็น