การเรียงลำดับแบบบับเบิ้ลคืออัลกอริธึมการเรียงลำดับเพื่อจัดเรียงรายการตามลำดับจากน้อยไปมาก (หรือจากมากไปน้อย) นี่เป็นอัลกอริธึมการเรียงลำดับที่ง่ายที่สุด แต่ก็ไม่ได้มีประสิทธิภาพมากนัก สามารถใช้กับอินพุตขนาดเล็กแต่ไม่มีประสิทธิภาพด้านเวลาสำหรับรายการหรืออาร์เรย์ที่มีความยาวมากขึ้น ความซับซ้อนของเวลาคือ O(n^2) อย่างไรก็ตาม นี่เป็นอัลกอริธึมการจัดเรียงแบบแทนที่ ซึ่งหมายความว่าจะไม่ใช้พื้นที่เพิ่มเติม ดังนั้นจึงมีประสิทธิภาพในแง่ของความซับซ้อนของพื้นที่ อย่างไรก็ตาม มีการใช้งานไม่มากนักเนื่องจากมีอัลกอริธึมการจัดเรียงที่ดีกว่าการจัดเรียงแบบฟอง
Bubble Sort ทำงานอย่างไร
ในการเรียงลำดับฟองจะใช้สองลูป วงรอบนอกวนซ้ำในรายการ inner for loop ยังวนซ้ำรายการสำหรับการวนซ้ำรอบนอกทั้งหมดด้วย
การดำเนินการหลักในการเรียงลำดับบับเบิ้ลคือการเปรียบเทียบสององค์ประกอบที่ต่อเนื่องกัน หากองค์ประกอบแรกมากกว่าองค์ประกอบถัดไป ให้สลับทั้งสองอย่างเพื่อให้องค์ประกอบที่เล็กกว่าอยู่ข้างหน้าและองค์ประกอบที่มากกว่าจะย้อนกลับ ในการวนซ้ำหนึ่งครั้งขององค์ประกอบที่ยิ่งใหญ่ที่สุดของรายการจะไปที่ดัชนีสุดท้าย ในการวนซ้ำครั้งที่สองของวงรอบนอก องค์ประกอบที่ใหญ่เป็นอันดับสองของรายการจะไปที่ดัชนีสุดท้ายที่สองและต่อไปเรื่อยๆ ดังนั้น เราจึงได้รับรายการที่จัดเรียงเมื่อสิ้นสุดการทำซ้ำทั้งหมด
เราสามารถเข้าใจได้ดีขึ้นด้วยความช่วยเหลือจากตัวอย่าง
ตัวอย่าง
เราจำเป็นต้องเรียงลำดับรายการต่อไปนี้
| 5 | 2 | 1 | 3 | 4 |
วงนอก=1
| 5 | 2 | 1 | 3 | 4 |
5>2 ดังนั้นสลับทั้งสองอย่าง
| 2 | 5 | 1 | 3 | 4 |
5>1 ดังนั้นสลับทั้งสองอย่าง
| 2 | 1 | 5 | 3 | 4 |
5>3 ดังนั้นสลับทั้งสองอย่าง
| 2 | 1 | 3 | 5 | 4 |
5>4 ดังนั้นสลับทั้งสองอย่าง
| 2 | 1 | 3 | 5 | 4 |
(องค์ประกอบที่ใหญ่ที่สุด 5 มาถึงดัชนีสุดท้ายหลังจากการวนซ้ำครั้งแรก)
วงนอก=2
| 2 | 1 | 3 | 5 | 4 |
2>1 ดังนั้นสลับ
| 1 | 2 | 3 | 5 | 4 |
ไม่ต้องเปลี่ยน
| 1 | 2 | 3 | 4 | 5 |
ไม่ต้องเปลี่ยน
| 1 | 2 | 3 | 4 | 5 |
ดังที่เราเห็นรายการถูกจัดเรียงในการวนซ้ำรอบที่ 2 นั้นเอง แต่วงรอบนอกจะวนซ้ำอีก 3 ครั้งโดยไม่มีการดำเนินการสลับเพิ่มเติม ดังนั้น ในตัวอย่างจะแสดงการวนซ้ำเพียง 2 ครั้งเท่านั้น บางครั้งรายการสามารถจัดเรียงในการวนซ้ำครั้งแรกได้ บางครั้ง รายการอาจถูกจัดเรียงในการวนซ้ำครั้งสุดท้าย ดังนั้น วงนอกจะวนซ้ำ n ครั้งเสมอ
ตัวอย่าง
def bubble_sort(arr): for i in range(len(arr)): for j in range(len(arr)-1): if(arr[j]>arr[j+1]): temp=arr[j] arr[j]=arr[j+1] arr[j+1]=temp return arr array=[2,3,1,5,4] print(bubble_sort(array))
ผลลัพธ์
[1, 2, 3, 4, 5]
