เรื่อง Sorting
การเรียงลำดับ (sorting)
เป็นการจัดให้เป็นระเบียบมีแบบแผน ช่วยให้การค้นหาสิ่งของ หรือข้อมูล ซึ่งจะสามารถกระทำได้รวด เร็วและมีประสิทธิภาพ เช่น การค้นหาความ หมายของคำใน พจนานุกรม ทำได้ค่อน ข้างง่ายและรวดเร็วเนื่องจากมี การเรียง ลำดับคำตามตัวอักษร ไว้อย่างมีระบบและเป็นระเบียบ
การเรียงลำดับอย่างมีประสิทธิภาพ
หลักเกณฑ์ในการพิจารณาเพื่อเลือกวิธีการเรียงลำดับที่ดี และ เหมาะสม กับระบบงาน เพื่อให้ประสิทธิภาพในการทำงานสูงสุด ควรจะต้องคำนึงถึง สิ่งต่าง ๆ ดังต่อไปนี้
(1) เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม
(2) เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตามโปรแกรมที่เขียน
(3) จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่
วิธีการเรียงลำดับสามารถแบ่งออกเป็น 2 ประเภทคือ
(1)การเรียงลำดับแบบภายใน (internal sorting)เป็นการเรียง ลำดับที่ ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก เวลาที่ใช้ ในการเรียงลำดับจะ คำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและ เลื่อนข้อมูลภายในความจำหลัก
(2) การเรียงลำดับแบบภาย นอก(external sorting) เป็นการ เรียงลำดับข้อมูลที่เก็บอยู่ใน หน่วยความ จำสำรอง ซึ่งเป็นการ เรียงลำดับข้อมูลในแฟ้ม ข้อมูล(file) เวลาที่ใช้ในการ เรียง ลำดับต้องคำนึงถึงเวลา ที่เสียไประหว่างการถ่ายเทข้อมูลจาก หน่วย ความจำหลักและ หน่วยความจำสำรองนอกเหนือจากเวลา ที่ใช้ในการเรียง ลำดับ ข้อมูลแบบภายใน
การเรียงลำดับแบบเลือก (selection sort)
ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ที ละตัวโดยทำ การค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับ ถ้าเป็นการเรียงลำดับจาก น้อยไปมาก
การเรียงลำดับ (sorting)
เป็นการจัดให้เป็นระเบียบมีแบบแผน ช่วยให้การค้นหาสิ่งของ หรือข้อมูล ซึ่งจะสามารถกระทำได้รวด เร็วและมีประสิทธิภาพ เช่น การค้นหาความ หมายของคำใน พจนานุกรม ทำได้ค่อน ข้างง่ายและรวดเร็วเนื่องจากมี การเรียง ลำดับคำตามตัวอักษร ไว้อย่างมีระบบและเป็นระเบียบ
การเรียงลำดับอย่างมีประสิทธิภาพ
หลักเกณฑ์ในการพิจารณาเพื่อเลือกวิธีการเรียงลำดับที่ดี และ เหมาะสม กับระบบงาน เพื่อให้ประสิทธิภาพในการทำงานสูงสุด ควรจะต้องคำนึงถึง สิ่งต่าง ๆ ดังต่อไปนี้
(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. ถ้าเป็นการเรียงลำดับจากน้อยไปมากให้ นำข้อมูลตัวที่มี ค่าน้อยกว่า อยู่ในตำแหน่งก่อนข้อมูลที่มีค่า มาก ถ้าเป็นการ เรียงลำดับจากมากไป น้อยให้นำข้อมูล ตัวที่ มีค่ามากกว่าอยู่ ในตำแหน่งก่อนข้อมูลที่มีค่าน้อย
-กำหนดให้มีข้อมูล n จำนวน การเปรียบเทียบเริ่มจากคู่แรก หรือคู่สุดท้าย ก็ได้ ถ้าเริ่มจากคู่สุดท้ายจะเปรียบเทียบข้อมูล ที่ตำแหน่ง n-1 กับ n ก่อน แล้วจัดเรียงให้อยู่ในตำแหน่งที่ถูก ต้อง ต่อไปเปรียบเทียบข้อมูลที่ตำแหน่ง n-2 กับ n-1 ทำเช่น นี้ไป เรื่อย ๆจนกระทั่งถึงข้อมูลตัวแรก และทำการ เปรียบ เทียบในรอบอื่นเช่นเดียวกันจนกระทั่งถึงรอบสุดท้ายที่เหลือ ข้อมูล 2 ตำแหน่งสุดท้าย เมื่อการจัดเรียงเสร็จเรียบร้อยทุก ตำแหน่งก็จะได้ข้อมูล เรียงลำดับตามที่ต้อง
การการเรียงลำดับแบบเร็ว (quick sort)
เป็นวิธีการเรียงลำดับที่ ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มี จำนวนมากที่ต้อง การความ รวดเร็วในการทำงาน วิธีนี้จะ เลือกข้อมูลจากกลุ่มข้อมูลขึ้นมา หนึ่ง ค่าเป็นค่าหลัก แล้ว หาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูก ต้องแล้ว ใช้ค่าหลักนี้เป็นหลักในการแบ่ง ข้อมูลออกเป็น สองส่วนถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่ ในตอนหน้าข้อมูล ทั้งหมดจะมีค่าน้อย กว่าค่าหลัก ที่เป็นตัว แบ่งส่วน อีกส่วนหนึ่งจะอยู่ในตำแหน่งตอนหลังข้อมูล ทั้งหมด จะมีค่ามากกว่าค่าหลักแล้วนำแต่ละส่วนย่อยไปแบ่ง ย่อยใน ลักษณะ เดียวกันต่อไปจนกระทั่งแต่ละส่วนไม่สามารถ แบ่ง ย่อยได้อีกต่อไปจะได้ข้อมูล ที่มีการเรียงลำดับตามที่ต้องการ
2. ใน รอบที่สองนำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บไว้ที่ ตำแหน่ง ที่สอง
3. ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกค่าในที่สุดจะได้ ข้อมูล เรียงลำดับจาก น้อยไปมากตามที่ต้องการ
-การจัดเรียงลำดับแบบเลือกเป็นวิธีที่ง่ายและตรงไปตรงมาแต่ มีข้อเสียตรงที่ ใช้เวลาในการจัดเรียงนาเพราะแต่ละรอบต้อง เปรียบเทียบกับข้อมูลทุกตัว ถ้า มีจำนวนข้อมูลทั้งหมดnตัวต้อง ทำการเปรียบเทียบทั้หมดn –1รอบและจำนวน ครั้งของการ เปรียบเทียบในแต่ละรอบเป็นดังนี้
รอบที่ 1 เปรียบเทียบเท่ากับ n −1 ครั้ง
รอบที่ 2 เปรียบเทียบเท่ากับ n – 2 ครั้ง
รอบที่ n – 1 เปรียบเทียบเท่ากับ 1 ครั้ง
การเรียงลำดับแบบฟอง (Bubble Sort)
เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลในตำแหน่งที่ อยู่ติดกัน
1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับ ตำแหน่ง ที่อยู่กัน
2. ถ้าเป็นการเรียงลำดับจากน้อยไปมากให้ นำข้อมูลตัวที่มี ค่าน้อยกว่า อยู่ในตำแหน่งก่อนข้อมูลที่มีค่า มาก ถ้าเป็นการ เรียงลำดับจากมากไป น้อยให้นำข้อมูล ตัวที่ มีค่ามากกว่าอยู่ ในตำแหน่งก่อนข้อมูลที่มีค่าน้อย
-กำหนดให้มีข้อมูล n จำนวน การเปรียบเทียบเริ่มจากคู่แรก หรือคู่สุดท้าย ก็ได้ ถ้าเริ่มจากคู่สุดท้ายจะเปรียบเทียบข้อมูล ที่ตำแหน่ง n-1 กับ n ก่อน แล้วจัดเรียงให้อยู่ในตำแหน่งที่ถูก ต้อง ต่อไปเปรียบเทียบข้อมูลที่ตำแหน่ง n-2 กับ n-1 ทำเช่น นี้ไป เรื่อย ๆจนกระทั่งถึงข้อมูลตัวแรก และทำการ เปรียบ เทียบในรอบอื่นเช่นเดียวกันจนกระทั่งถึงรอบสุดท้ายที่เหลือ ข้อมูล 2 ตำแหน่งสุดท้าย เมื่อการจัดเรียงเสร็จเรียบร้อยทุก ตำแหน่งก็จะได้ข้อมูล เรียงลำดับตามที่ต้อง
การการเรียงลำดับแบบเร็ว (quick sort)
เป็นวิธีการเรียงลำดับที่ ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มี จำนวนมากที่ต้อง การความ รวดเร็วในการทำงาน วิธีนี้จะ เลือกข้อมูลจากกลุ่มข้อมูลขึ้นมา หนึ่ง ค่าเป็นค่าหลัก แล้ว หาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูก ต้องแล้ว ใช้ค่าหลักนี้เป็นหลักในการแบ่ง ข้อมูลออกเป็น สองส่วนถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่ ในตอนหน้าข้อมูล ทั้งหมดจะมีค่าน้อย กว่าค่าหลัก ที่เป็นตัว แบ่งส่วน อีกส่วนหนึ่งจะอยู่ในตำแหน่งตอนหลังข้อมูล ทั้งหมด จะมีค่ามากกว่าค่าหลักแล้วนำแต่ละส่วนย่อยไปแบ่ง ย่อยใน ลักษณะ เดียวกันต่อไปจนกระทั่งแต่ละส่วนไม่สามารถ แบ่ง ย่อยได้อีกต่อไปจะได้ข้อมูล ที่มีการเรียงลำดับตามที่ต้องการ
การเรียงลำดับแบบแทรก (insertion sort)
เป็นวิธีการเรียงลำดับที่ ทำการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มีสมาชิกทุกตัว เรียงลำดับ อยู่แล้ว และทำให้เซตใหม่ที่ได้ นี้มีสมาชิกทุกตัวเรียงลำดับด้วย วิธีการเรียงลำดับจะ. เริ่มต้น เปรียบเทียบจากข้อมูลในตำแหน่งที่
1 กับ 2หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้ายก็ได้ถ้า เป็นการเรียงลำดับ จากน้อยไปมากจะต้องจัดให้ข้อมูลที่มีค่า น้อยอยู่ในตำแหน่งก่อนข้อมูลที่มีค่า มากและถ้าเรียงจากมาก ไปน้อยจะก็ จะจัดให้ข้อมูลที่มีค่ามากอยู่ในตำแหน่งก่อน เช่น ต้องการเรียงลำดับข้อมูลจากน้อยไปมาก และเริ่มต้นนำ ข้อมูล
2 ตัวแรกมา เปรียบเทียบ ให้ข้อมูลที่มีค่าน้อยกว่าอยู่ใน ตำแหน่งแรก จะได้ข้อมูลในเซตที่เรียง ลำดับแล้วมีสมาชิก 2 ตัว จากนั้นนำสมาชิก ใหม่เข้ามาโดยเริ่มเปรียบเทียบกับ สมาชิกในเซตทีละตัว จะเริ่มเปรียบ เทียบตั้งแต่ตัวแรกหรือ ตัวหลังสุดก็ได้ ถ้า เปรียบเทียบตั้งแต่ตัวแรกจะต้องหาตำแหน่ง สมาชิกที่มีค่ามากกว่าสมาชิกใหม่แล้ว ทำการถอยทุก ค่าไป หนึ่ตำแหน่งตั้งแต่ตำแหน่งนั้นเป็นต้นไป เพื่อให้เกิดตำแหน่งว่าง สำหรับแทรกสมาชิกใหม่ลงไปก็จะได้เซตที่เรียงลำดับใหม่
การเรียงลำดับแบบฐาน (radix sort)
เป็นการเรียงลำดับโดยการ พิจารณาข้อมูลทีละหลัก1.เริ่มพิจารณา จากหลักที่มีค่า น้อยที่สุด ก่อนนั่นคือถ้าข้อมูลเป็นเลขจำนวนเต็มจะ พิจารณาหลักหน่วยก่อน
2.การจัดเรียงจะนำข้อมูลเข้ามาทีละตัวแล้วนำไปเก็บไว้ที่ซึ่งจัด ไว้ สำหรับค่านั้น เป็นกลุ่มๆตามลำดับกาเข้ามา
3. ในแต่ละรอบเมื่อ จัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุก กลุ่มเข้าด้วยกัน โดยเริ่มเรียงจากกลุ่มที่มีค่าน้อยที่สุดก่อนแล้วเรียง ไปเรื่อย ๆ จนหมดทุกกลุ่ม
4. ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียง ในหลักหน่วยเรียบร้อย แล้วมาพิจารณา จัดเรียงในหลักสิบต่อไป ทำเช่นนี้ไปเรื่อย ๆ จนกระ ทั่ง ครบทุกหลักจะได้ข้อมูลที่เรียง ลำดับ จากน้อยไปมากตามต้องการ
ไม่มีความคิดเห็น:
แสดงความคิดเห็น