Algorithm การจัดเรียงข้อมูลแบบ Bubble Sort

สวัสดีครับ ในบทความนี้จะเป็นการแนะนำ Algorithm การจัดเรียงข้อมูล มีหลายวิธี เช่น Quicksort, Mergesort, Insertion Sort Bubble Sort, Bucket Sort, Radix Sort และ Heapsort ซึ่งแต่ละตัวจะมีประสิทธิภาพในการทำงานที่แตกต่างกัน ซึ่งส่วนใหญ่ในทางคอมพิวเตอร์จะใช้ Big O notation ในการบ่งบอกว่า Algorithm ดังกล่าวจะใช้เวลานานเท่าใด

Bubble Sort

Bubble Sort เป็น Algorithm ที่ประสิทธิภาพในการทำงานเร็วสุดที่ O(n) เฉลี่ย O(n²) แย่สุด O(n²) ซึ่งยังถือว่าช้า และยิ่งข้อมูลมากเท่าไหร่ก็ช้ามากขึ้นตาม แต่ Bubble Sort เป็นการจัดเรียงข้อมูลที่เข้าใจง่ายที่สุด เหมาะแก่การเริ่มต้นเรียนรู้ Algorithm

วิธีการคือ จะสร้างลูปขึ้นมาสองลูปดังนี้ (ยกตัวอย่างเป็นภาษา Python)

def bubblesort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-1):
            if(arr[j] > arr[j+1]):
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
    return arr

หมายความว่า จะมีสองลูปในโปรแกรมโดยลูปแรกจะไล่ตั้งแต่ตัวแรกของ array ไปจนถึงตัวสุดท้าย หรือทำซ้ำจำนวนเท่ากับขนาดของ array ในขณะที่ลูปแรกทำงาน ลูปที่สองจะเช็ค array ปัจจุบัน และ array ถัดไปว่า array ปัจจุบันมีค่ามากกว่าหรือไม่ หากมากกว่าก็จะสลับ เมื่อลูปที่สองทำการสลับตั้งแต่ตัวแรกจนถึงตัวรองสุดท้าย (n-1) ได้หนึ่งรอบ ลูปแรกก็จะทำงานผ่านไปหนึ่งครั้ง ทำให้ลูปที่สองเริ่มเช็คที่ตัวแรกอีกครั้งไปจนถึงตัวสุดท้าย เมื่อทำซ้ำจนครบลูปแรก ข้อมูลก็จะถูกจัดเรียงเป็นที่เรียบร้อย

[12,7,4,1,14,3,8,6]

อ้างอิง: https://www.geeksforgeeks.org/python-program-for-bubble-sort/