Google        youtube          psv       สพม.11

แบบฝึก(เฉลย)การจัดเรียงลำดับข้อมูล

ตอนที่ 1 อธิบาย

1. จงอธิบายความแตกต่างระหว่างการเรียงลำดับภายในกับการเรียงลำดับภายนอกเป็นอย่างไร

ตอบ

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

2. จงอธิบายการเรียงลำดับที่มีการเปรียบเทียบ O(n2) มีวิธีการแบบใดบ้าง

ตอบ

1. การเรียงลำดับแบบดับเบิ้ล  (Bubble Sort)

2. การเรียงลำดับแบเลือก  (Selection Sort)

3. การเรียงลำดับแบแทรก  (Insertion Sort)

4. การเรียงลำดับแบบเชล์   (Shell Sort)

3. จงอธิบายการเรียงลำดับที่ไม่มีการเปรียบเทียบมีวิธีแบบใดบ้าง

ตอบ

1. การเรียงลำดับแบบนับจำนวน(Countinq Sort)

2. การเรียงลำดับแบบเรดิกซ์(Radix Sort)

4. จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 60, 50, 70, 10, 40, 20 ถ้าต้องการเรียงลำดับแบบบับเบิลจากค่า   มากไปหาน้อย ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ จะต้องใช้การจัดเรียงลำดับกี่รอบ และมีการสลับตำแน่งกันทั้งหมดกี่ครั้ง

ตอบ

 

 

 

 

5. จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 30, 50, 70, 10, 40, 60 ถ้าต้องการเรียงลำดับแบบเลือกจากค่า   มากไปหาน้อย ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ จะต้องใช้การจัดเรียงลำดับกี่รอบ และมีการสลับตำแน่งกันทั้งหมดกี่ครั้ง

ตอบ

6. จงอธิบายและแสดงขั้นตอนการเรียงลำดับแบบเชลล์เป็นอย่างไร

ตอบ

การจัดเรียงลำดับแบบเซล์หรือจำนวนลำดับแบบจำนวนเพิ่มๆค่อยลดลง (Diminishing Incremeny Sort) จะใช้เรียงลำดับแบบแทรกกับกลุ่มย่อยของค่าตามลำดับ กลุ่มย่อยเหล่านี้จะถูกเลือกใช้ในทิศทางพยายามให้ค่าถูกเรียงมากสุดก่อนที่จะใช้ การเรียงลำดับแบบแทรก ก็จะได้เวลาการทำงานที่ใช้การเรียงลำดับแบบแทรกในแต่ละรอบเกือบเป็นเส้นตรง

7. จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 45, 20, 50, 30, 80, 10, 60, 70, 40, 90 ถ้าต้องการเรียงลำดับแบบรวดเร็ว ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ

ตอบ

8. จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 20, 15, 31, 10, 67, 50, 3, 49, 26 ถ้าต้องการเรียงลำดับแบบ

ฮีพ ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ

ตอบ

9.จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 322, 715, 931, 250, 176, 845, 463, 192, 526 ถ้าต้องการเรียงลำดับแบบเรดิกซ์ ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ

ตอบ

10. จงอธิบายการเรียงลำดับและผสานแฟ้มข้อมูลเป็นอย่างไร

ตอบ

11. จงอธิบายและแสดงขั้นตอนการเรียงลำดับและผสานหลายขั้นตอนเป็นอย่างไร

ตอบ

12.จากอาร์เรย์ x มีค่าของสมาชิกเป็น 84, 19, 31, 25, 12, 53, 99, 68, 49, 77, 43, 30, 62, 11, 97, 80, 21, 37, 79, 55, 15, 58, 71, 23, 94, 66, 29, 63, 57, 81 จงเรียงลำดับและผสานแฟ้มข้อมูลโดยใช้การเรียงลำดับและผสานสมดุล ให้หนึ่งรันมี 3 เรคคอร์ดและมี 4 ม้วนเทป

ตอบ

ตอนที่ 2 อธิบายคำศัพท์

1. Internal Sorting

ตอบ การเรียงลำดับภายใน

2. Inplace Sorting

ตอบ พื้นที่หน่วยความจำของตนเอง

3. Stable Sort

ตอบ

4. Comparison Sort

ตอบ การเรียงลำดับมีการเปรียบเทียบ

5. Insertion Sort

ตอบ การเรียงลำดับแบบแทรก

6. Merge Sort

ตอบ การเรียงลำดับแบบผสมผสาน

7. Average Case

ตอบ กรณีเฉลี่ย

8. Binary Insertion Sort

ตอบ การเรียงลำดับแบบแทรกโดยแบ่งครึ่ง

9. Divide-and-Conquer

ตอบ วีธีการแบ่งและยึดรวมกัน

10. Logarithmic Time

ตอบ การทำงานที่ใช้เวลาเป็นลอกการิทึม

11. Tally Sort

ตอบ การเรียงลำดับแบบยอดรวมสูงสุด

12. Tournament Sort

ตอบ

13. Sort/Merge

ตอบ

 

14. M-way Natural Merge

ตอบ การผสมผสานธรรมดา M ทาง

15. Polyphase Merge

ตอบ การผสมผสานหลายขั้นตอน

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s