warayuphat panumphan 'Kru Pu'

ทดสอบหลัง final

การจัดเรียงข้อมูลแบบ 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 --> สลับค่า)
4 5 3 2 1 (เปรียบเทียบข้อมูลตัวที่ 2 กับตัวที่ 3 : ตัวที่ 2 มากกว่า ตัวที่ 3 --> สลับค่า)
4 3 5 2 1 (เปรียบเทียบข้อมูลตัวที่ 3 กับตัวที่ 4 : ตัวที่ 3 มากกว่า ตัวที่ 4 --> สลับค่า)
4 3 2 5 1 (เปรียบเทียบข้อมูลตัวที่ 4 กับตัวที่ 5 : ตัวที่ 4 มากกว่า ตัวที่ 5 --> สลับค่า)
4 3 2 1 5

Bubble Sort ครั้งที่ 2

4 3 2 1 5 (เปรียบเทียบข้อมูลตัวที่ 1 กับตัวที่ 2 : ตัวที่ 1 มากกว่า ตัวที่ 2 --> สลับค่า)
3 4 2 1 5 (เปรียบเทียบข้อมูลตัวที่ 2 กับตัวที่ 3 : ตัวที่ 2 มากกว่า ตัวที่ 3 --> สลับค่า)
3 2 4 1 5 (เปรียบเทียบข้อมูลตัวที่ 3 กับตัวที่ 4 : ตัวที่ 3 มากกว่า ตัวที่ 4 --> สลับค่า)
3 2 1 4 5 (เปรียบเทียบข้อมูลตัวที่ 4 กับตัวที่ 5 : ตัวที่ 4 น้อยกว่า ตัวที่ 5 --> ไม่ต้องสลับค่า)
3 2 1 4 5

Bubble Sort ครั้งที่ 3

3 2 1 4 5 (เปรียบเทียบข้อมูลตัวที่ 1 กับตัวที่ 2 : ตัวที่ 1 มากกว่า ตัวที่ 2 --> สลับค่า)
2 3 1 4 5 (เปรียบเทียบข้อมูลตัวที่ 2 กับตัวที่ 3 : ตัวที่ 2 มากกว่า ตัวที่ 3 --> สลับค่า)
2 1 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 3 กับตัวที่ 4 : ตัวที่ 3 น้อยกว่า ตัวที่ 4 --> ไม่ต้องสลับค่า)
2 1 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 4 กับตัวที่ 5 : ตัวที่ 4 น้อยกว่า ตัวที่ 5 --> ไม่ต้องสลับค่า)
2 1 3 4 5

Bubble Sort ครั้งที่ 4

2 1 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 1 กับตัวที่ 2 : ตัวที่ 1 มากกว่า ตัวที่ 2 --> สลับค่า)
1 2 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 2 กับตัวที่ 3 : ตัวที่ 2 มากกว่า ตัวที่ 3 --> ไม่ต้องสลับค่า)
1 2 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 3 กับตัวที่ 4 : ตัวที่ 3 น้อยกว่า ตัวที่ 4 --> ไม่ต้องสลับค่า)
1 2 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 4 กับตัวที่ 5 : ตัวที่ 4 น้อยกว่า ตัวที่ 5 --> ไม่ต้องสลับค่า)
1 2 3 4 5

เมื่อทำครบ 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];
num[1]=num[0];

แต่ถ้าหากเรามาพิจารณาดูแล้ว จะพบว่ามันผิด ดังนี้

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>
using namespace std;
int main()
{  int i, temp, round;
int x[5]={9, 7, 5, 3, 1};
cout<<"The Bubble sort array\n";
for(i=0; i<5; i++)
cout<< x[i];
cout<<"\n";
for(round=0; round<5-1; round++)
for(i=0; i<5-1-round; i++)
{
if(x[i]>x[i+1])
{
temp = x[i]; 
x[i] = x[i+1];
x[i+1] = temp;
}
}
cout<<"Final the Bubble sorted array\n";
for(i=0; i<5; i++)
cout<< x[i]; 
cout<<"\n";
return 0 ;
}

แบบฝึกหัดที่ 1

ให้นักเรียนเรียงข้อมูลข้างต้น จากมากไปหาน้อย

แบบฝึกหัดที่ 2

1. ระบบรักษาความปลอดภัยของธนาคารแห่งหนึ่ง มีวิธีการตรวจสอบรหัสที่ป้อนเข้าไปในระบบ โดยในขั้นแรกระบบจะใช้เลขเวกัสของรหัสนั้นในการตรวจสอบ โดยถ้าเลขเวกัสของรหัสนั้นเป็นจำนวนที่หารด้วย 2 ลงตัว จะผ่านการตรวจสอบในขั้นที่ 1 ของระบบ แต่ถ้าหากหารไม่ลงตัวจะถือว่ารหัสนั้นผิด

โดยเลขเวกัส คือ (ค่าสูงสุดลำดับที่ 1 ของข้อมูล - ค่าสูงสุดลำดับที่ 2 ของข้อมูล) * ค่าสูงสุดลำดับที่ 9 ของข้อมูล
ยกตัวอย่างเช่น

รหัส 321546789 มีเลขเวกัสเท่ากับ (9-8)*1=1
รหัส 777777778 มีเลขเวกัสเท่ากับ (8-7)*7=7 เป็นต้น

ให้รับข้อมูลจากผู้ใช้เป็นเลข 9 หลัก จากนั้นให้ตรวจสอบรหัสที่ป้อนเข้าไป
ถ้าหากรหัสนั้นผ่านการตรวจสอบขั้นที่ 1 ให้แสดง Correct ออกทางจอภาพ
แต่ถ้าหากรหัสนั้นไม่ผ่านการตรวจสอบขั้นที่ 1 แล้ว ให้แสดง Error ออกทางจอภาพ