คำตอบของทีม
ไม่ได้ส่งคำตอบ
คะแนน + โบนัสทำเร็ว
0.0
แชร์
ไม่ได้ส่งคำตอบ
พิจารณารายการตัวเลขต่อไปนี้
$\quad$10$\quad$30$\quad$20$\quad$15
เราต้องการจัดเรียงตัวเลขในรายการนี้ให้เรียงลำดับจากน้อยไปหามาก โดยทำได้โดยสลับตัวเลขคู่ที่อยู่ติดกันเท่านั้น ยกตัวอย่างเช่น จากลำดับข้างต้นเราสามารถสลับลำดับ 30 กับ 20 ได้ แต่ไม่สามารถสลับ 15 กับ 30 ได้
จากรายการข้างต้นเราสามารถสลับให้รายการเรียงลำดับได้โดยใช้การสลับน้อยที่สุด 3 ครั้ง ดังนี้



พิจารณารายการตัวเลขต่อไปนี้
$\quad$10$\quad$20$\quad$13$\quad$30$\quad$44$\quad$17$\quad$19$\quad$11$\quad$99

เราสามารถจัดเรียงลำดับได้โดยใช้การสลับเฉพาะตัวเลขที่ติดกัน โดยใช้การสลับเป็นจำนวนครั้งน้อยที่สุดกี่ครั้ง

1) 9 ครั้ง
2) 10 ครั้ง
3) 12 ครั้ง
4) 13 ครั้ง
เฉลย

ตอบ 4) 13 ครั้ง

แนวคิด

สามารถหาคำตอบโดยการเขียนโปรแกรมจัดเรียงข้อมูลที่สลับเฉพาะตัวเลขติดกัน เช่น bubble sort หรือ insertion sort และนับจำนวนครั้งในการสลับ จำนวนครั้งในการสลับคือ 13 ครั้ง

อีกวิธีหนึ่งที่ไม่จำเป็นต้องเขียนโปรแกรมจัดเรียงข้อมูล

เราสามารถนับจำนวนคู่ของข้อมูลทั้งหมดที่อยู่ในลำดับที่ผิด เช่น 20 กับ 17 อยู่ในลำดับที่ผิด ดังนั้นในระหว่างการสลับจะต้องมีการสลับครั้งหนึ่งที่ 20 กับ 17 อยู่ติดกันและโดนสลับ  จำนวนคู่ที่อยู่ในลำดับที่ผิดคือ 13 เท่ากับจำนวนครั้งน้อยที่สุดในการสลับเฉพาะตัวเลขที่ติดกัน