การจัดเรียงข้อมูลแบบ 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
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
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
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
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 ครั้ง เราก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมาก
Algorithms Bubble Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| <script>var a = [4, 1, 3, 5, 2, 6]; function bubbleSort(a){ var swapped; do { swapped = false; for (var i=0; i < a.length-1; i++) { if (a[i] > a[i+1]) { var temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; swapped = true; } } } while (swapped);}console.log(a); bubbleSort(a);console.log(a);</script> |
ไม่มีความคิดเห็น:
แสดงความคิดเห็น