DTS10-09-09-2552

สรุปสิ่งที่ได้รับในการเรียนเรื่อง SORTING

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

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

การจัดเรียงข้อมูลแบบเบื้องต้น

1. การจัดเรียงข้อมูลแบบเลือก (Selection Sort) มีหลักการของการจัดเรียง คือ เลือกค่าข้อมูลที่น้อยหรือมากที่สุดอย่างใดอย่างหนึ่งในแต่ละฐานข้อมูลเป็นตัวหลัก จากนั้นนำมาจัดเรียงแบบลำดับเลือกข้อมูลตัวต่อไปจนจัดเรียงเสร็จ เช่น ข้อมูล 1 ชุด ประกอบด้วย 390 205 182 45 235 จากข้อมูลชุดนี้ หากนำมาจัดเรียงแบบเลือกจัดลำดับค่าต่ำสุดไปหาค่าสูงสุดได้ดังนี้จากตารางแสดงการจัดเรียงข้อมูลแบบเลือกของชุดข้อมูลทั้ง 5 ตัวในแนวตั้ง คือ
ครั้งที่ 1 เลือกข้อมูลที่มีค่าน้อยที่สุดมาจัดเรียงลำดับสลับตำแหน่งระหว่าง 45 และ 390
ครั้งที่ 2 เลือกข้อมูลที่น้อยลงมาเป็นอันดับที่ 2 คือ 182 ไปสลับกับ 205 ในตำแหน่งที่ 2
ครั้งที่ 3 เลือกข้อมูลที่น้อยลงมาเป็นอันดับที่ 3 คือ 205 ซึ่งอยู่ในตำแหน่งเดิม
ครั้งที่ 4 เลือกข้อมูลที่น้อยลงมาเป็นอันดับที่ 4 คือ 235 ไปสลับกับ 390 ในตำแหน่งที่ 4
จึงไม่มีครั้งที่ 5 เพราะข้อมูลได้มีการจัดเรียงลำดับครบทุกตัวแล้ว

2. การจัดเรียงข้อมูลแบบฟอง (Bubble Sort) เป็นรูปแบบของการจัดเรียงแบบแลกเปลี่ยนเนื่องจากลักษณะของการจัดเรียงจะใช้การเปรียบเทียบค่าใน 2 ตำแหน่งใกล้เคียงเรียงลำดับการจัดจากมากไปน้อยหรือจากน้อยไปมาก จากนั้นจะเปลี่ยนตำแหน่งกันแล้วใช้ตำแหน่งที่ 2 เปรียบเทียบกับตารางที่ 3 ไปจนถึงตำแหน่งที่ n จนเสร็จสิ้นการจัดเรียง เช่น จากข้อมูล 390 205 182 45 235 นำมาจัดเรียงแบบบับเบิ้ลได้ดังตาราง

จากตารางแสดงการจัดเรียงข้อมูลแบบบับเบิ้ลในรอบที่ 1 ทำการเปรียบเทียบค่าแล้วเลื่อนค่าลงเปรียบเทียบกับตำแหน่งต่อไป ในรอบที่ 1 นี้จะทำการเปรียบเทียบอยู่ 4 ครั้ง คือ
ครั้งที่ 1 เปรียบเทียบข้อมูลกับตำแหน่งที่ 1,2 ข้อมูล 390>205 เปลี่ยนตำแหน่ง 205 ไว้ด้านบน
ครั้งที่ 2 เปรียบเทียบข้อมูลกับตำแหน่งที่ 2,3 ข้อมูล 390>182 เปลี่ยนตำแหน่ง 182 ไว้ด้านบน
ครั้งที่ 3 เปรียบเทียบข้อมูลกับตำแหน่งที่ 3,4 ข้อมูล 390>45 เปลี่ยนตำแหน่ง 45 ไว้ด้านบน
ครั้งที่ 4 เปรียบเทียบข้อมูลกับตำแหน่งที่ 4,5 ข้อมูล 390>235 เปลี่ยนตำแหน่ง 235 ไว้ด้านบน
จะเห็นว่าข้อมูลที่จัดเรียงได้ค่า 205 182 45 235 390 ซึ่งยังไม่เสร็จสิ้น จึงต้องทำการเปรียบเทียบค่าอีกโดยใช้วิธีการเดิมในรอบที่ 2

ข้อมูลที่ได้จากการจัดเรียงในรอบที่ 2 คือ 182 45 205 235 390 ซึ่งในรอบนี้จะเห็นว่าการเปรียบเทียบค่านั้นจะเปรียบเทียบเพียงแค่ 2 ครั้งเพราะค่าหลัง 205 นั้นมีค่ามากกว่าแล้วจึงไม่ดำเนินการต่อแต่ยังต้องเรียงลำดับข้อมูลต่อในรอบที่ 3

จากตารางเป็นการจัดเรียงข้อมูลแบบบับเบิ้ลในรอบที่ 3 ข้อมูลมีการจัดเรียงแบบบับเบิ้ลเสร็จ โดยเรียงจากน้อยไปหามากได้ข้อมูล 45 182 205 235 390 จะเห็นว่าใช้การจัดเรียงที่มีจำนวนครั้งในการจัดเรียงแต่ละรอบหลายครั้งกว่าจะได้ข้อมูลออกมา แต่ในบางรอบของการจัดเรียง ข้อมูลที่ได้มีการจัดเรียงถูกต้องแล้วก็จะไม่นำมาเปรียบเทียบค่าอีก

3. การจัดเรียงข้อมูลแบบแทรก (Insertion Sorting) จะใช้หลักการของการจัดเรียงที่ว่ากำหนดพื้นที่ออกเป็น 2 ส่วน ส่วนแรกใช้ในการจัดข้อมูลที่เรียงลำดับแล้วและอีกส่วนคือ ข้อมูลที่ยังไม่ได้จัดเรียง นำเอาข้อมูลที่ยังไม่ได้จัดเรียงมาแทรกยังตำแหน่งที่ถูกต้องด้านที่ใช้จัดเรียงลำดับ และดำเนินการต่อไปจนกว่าการจัดเรียงจะถูกต้อง เช่น ข้อมูลชุด 23 78 45 8 32 56 สามารถจัดเรียงได้ดังภาพ

จากภาพ แสดงการแบ่งพื้นที่ในการจัดเรียงข้อมูลจะกำหนดพื้นที่ส่วนหน้าเป็นพื้นที่จัดเรียงข้อมูล พื้นที่ส่วนหลังใช้ในการเก็บข้อมูลที่ยังไม่ได้จัดเรียง หากนำข้อมูลมาจากพื้นที่ด้านหลังก็จะนำมาแทรกยังตำแหน่งที่ถูกต้องด้านหน้า ซึ่งจะได้ข้อมูลการจัดเรียงแบบถูกต้องคือ 8 23 32 45 56 78

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

การเรียงลำดับแบบฐานมีวิธีการที่ไม่ซับซ้อน แต่ค่อนข้างใช้เนื้อที่ในหน่วยความจำมาก เนื่องจากการจัดเรียงแต่ละรอบจะต้องเตรียมเนื้อที่สำหรับสร้างที่เก็บข้อมูลในแต่ละกลุ่ม เช่น ถ้ามีจำนวนข้อมูล n ตัว และในแต่ละกลุ่มใช้วิธีจัดเก็บข้อมูลในแถวลำดับ ต้องกำหนดให้แต่ละกลุ่มมีสมาชิกได้ n ตัว เท่ากับจำนวนข้อมูล เผื่อไว้ในกรณีที่ข้อมูลทั้งหมดมีค่าในหลักนั้นๆ เหมือนกัน ถ้าเป็นเลขจำนวนใช้ทั้งหมด 10 กลุ่ม กลุ่มละ n ตัว รวมทั้งหมดมีขนาดเท่ากับ (10 x n)