แบบเรียน ม.3
อบรมครู KM
สื่อดิจิตอล ( Digital media )
แบบทดสอบ Online
สถิติผู้เข้าชม
![]() | Today | 481 |
![]() | Yesterday | 524 |
![]() | This Week | 2844 |
![]() | This Month | 14354 |
![]() | All Days | 867145 |
ROBOT TEAM
วิทยาการคำนวณ
warayuphat panumphan 'Kru Pu', Powered by Joomla!
Bubble Sort |
![]() |
![]() |
![]() |
Written by Administrator | ||||||
Monday, 03 December 2012 08:32 | ||||||
การจัดเรียงข้อมูลแบบ Bubble Sort การเรียงข้อมูลแบบ Bubble Sort จะทำโดยการเปรียบเทียบค่าข้อมูลที่อยู่ติดกันทีละคู่ไปเรื่อยๆ ในกรณีเรียง ลำดับข้อมูลจากน้อยไปมาก ถ้าค่าแรกมีค่ามากกว่าค่าสองก็จะทำการสลับที่กัน โดยวิธีการนี้ จะทำให้ ข้อมูลที่มีค่าน้อยกว่าลอยสูงขึ้นเรื่อยเหมือนฟองสบู่(bubble) ที่ลอยขึ้นที่สูง และข้อมูลที่น้อยที่สุดก็จะ อยู่ในต่ำแหน่งบนสุดของชุดข้อมูลจึงเรียกการเรียงลำดับวิธีนี้ว่า BUBBLE SORT สมมติว่าต้องการเรียงข้อมูลจากน้อยไปมาก จะทำการเปรียบเทียบข้อมูลทีละ 2 ตัว ถ้าข้อมูลตัวแรกมากกว่าจะทำการสลับค่ากับข้อมูลตัวที่ 2 และเปรียบเทียบข้อมูลอีก 2 ตัวถัดไปจนสุดอาร์เรย์ จากนั้นทำซ้ำแบบเดิมอีกตามจำนวนข้อมูลในอาร์เรย์-1 เช่น ถ้าข้อมูลในอาร์เรย์มีจำนวน 5 ช่อง ก็ต้องทำซ้ำเป็นจำนวน 4 ครั้ง เป็นต้น กำหนดให้มีจำนวนเต็ม 5 จำนวน คือ 5 4 3 2 1 Bubble Sort ครั้งที่ 1 5 4 3 2 1 (เปรียบเทียบข้อมูลตัวที่ 1 กับตัวที่ 2 : ตัวที่ 1 มากกว่า ตัวที่ 2 --> สลับค่า) Bubble Sort ครั้งที่ 2 4 3 2 1 5 (เปรียบเทียบข้อมูลตัวที่ 1 กับตัวที่ 2 : ตัวที่ 1 มากกว่า ตัวที่ 2 --> สลับค่า) Bubble Sort ครั้งที่ 3 3 2 1 4 5 (เปรียบเทียบข้อมูลตัวที่ 1 กับตัวที่ 2 : ตัวที่ 1 มากกว่า ตัวที่ 2 --> สลับค่า) Bubble Sort ครั้งที่ 4 2 1 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 1 กับตัวที่ 2 : ตัวที่ 1 มากกว่า ตัวที่ 2 --> สลับค่า) เมื่อทำครบ 4 ครั้ง เราก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมาก ดู youtube การสลับตำแหน่งของข้อมูล แบบ Bubble Sort งาน Bubble Sort M.5/7 - 2556 กลุ่มที่1 กลุ่มที่2 งาน Bubble Sort M.5/2 - 2557 กลุ่มที่1 กลุ่มที่2 กลุ่มที่3 กลุ่มที่4 งาน Bubble Sort M.5/4 - 2557 กลุ่มที่1 กลุ่มที่2 กลุ่มที่3 กลุ่มที่4 กลุ่มที่5 กลุ่มที่6 งาน Bubble Sort M.5/5 - 2557 กลุ่มที่1 กลุ่มที่2 กลุ่มที่3 กลุ่มที่4 กลุ่มที่5 กลุ่มที่6 งาน Bubble Sort M.5/6 - 2557 กลุ่มที่1 กลุ่มที่2 กลุ่มที่3 กลุ่มที่4 กลุ่มที่5 งาน Bubble Sort M.5/7 - 2557 กลุ่มที่1 กลุ่มที่2 กลุ่มที่3 กลุ่มที่4 กลุ่มที่5 กลุ่มที่6 กลุ่มที่7 ขอขอบคุณเพลงประกอบการทำงานกลุ่ม ทุกค่ายเพลง มา ณ โอกาศนี้. การสลับค่าข้อมูลในอาร์เรย์
กำหนดให้มีอาร์เรย์เก็บจำนวนเต็มจำนวน 5 ช่อง num = 5 4 3 2 1; ถ้าหากต้องการสลับค่าข้อมูลตัวที่ 1 กับตัวที่ 2 โดยทั่วไปแล้วเรามักจะเขียนโค้ดว่า num[0]=num[1]; แต่ถ้าหากเรามาพิจารณาดูแล้ว จะพบว่ามันผิด ดังนี้ 5 4 3 2 1 num[0]=num[1]; 4 4 3 2 1 num[1]=num[0]; 4 4 3 2 1 เราจะพบว่า จำเป็นที่จะต้องมีตัวแปรหนึ่งตัว(ให้ชื่อว่า temp) ที่เก็บค่าข้อมูลตัวที่ 1 ไว้ชั่วคราว จากนั้นจึงค่อยสลับค่าดังนี้ 5 4 3 2 1 temp=num[0]; temp=5 num[0]=num[1]; 4 4 3 2 1 num[1]=temp; 4 5 3 2 1
เมื่อเราทราบวิธีการสลับค่าข้อมูล และวิธีการเรียงแบบ Bubble Sort แล้วเราก็สามารถนำมาประยุกต์ใช้สำหรับการจัดเรียงข้อมูลในอาร์เรย์ได้
int num[5]={5,4,3,2,1}; int i,j,temp; for(i=0;i<4;i++){ for(j=0;j<4;j++){ if(num[j]>num[j+1]){ temp=num[j]; num[j]=num[j+1]; num[j+1]=temp; } } } ตัวอย่าง การจัดเรียงข้อมูล 5 ค่าจากน้อยไปหามาก เลข 9 7 5 3 1 แบบ bubble sort #include <iostream> แบบฝึกหัดที่ 1 ให้นักเรียนเรียงข้อมูลข้างต้น จากมากไปหาน้อย แบบฝึกหัดที่ 2 1. ระบบรักษาความปลอดภัยของธนาคารแห่งหนึ่ง มีวิธีการตรวจสอบรหัสที่ป้อนเข้าไปในระบบ โดยในขั้นแรกระบบจะใช้เลขเวกัสของรหัสนั้นในการตรวจสอบ โดยถ้าเลขเวกัสของรหัสนั้นเป็นจำนวนที่หารด้วย 2 ลงตัว จะผ่านการตรวจสอบในขั้นที่ 1 ของระบบ แต่ถ้าหากหารไม่ลงตัวจะถือว่ารหัสนั้นผิด โดยเลขเวกัส คือ (ค่าสูงสุดลำดับที่ 1 ของข้อมูล - ค่าสูงสุดลำดับที่ 2 ของข้อมูล) * ค่าสูงสุดลำดับที่ 9 ของข้อมูล รหัส 321546789 มีเลขเวกัสเท่ากับ (9-8)*1=1 ให้รับข้อมูลจากผู้ใช้เป็นเลข 9 หลัก จากนั้นให้ตรวจสอบรหัสที่ป้อนเข้าไป
|
||||||
Last Updated on Wednesday, 07 January 2015 04:43 |