ทำความรู้จักกับ Bubble Sort: อัลกอริธึมเรียงลำดับที่ง่าย แต่ยังมีเสน่ห์

 

ในโลกของการเขียนโปรแกรมและการพัฒนาซอฟต์แวร์ อัลกอริธึมการเรียงลำดับ (Sorting Algorithm) เป็นส่วนสำคัญที่เราต้องทำความเข้าใจเพื่อนำไปใช้ในการจัดการข้อมูลให้มีระเบียบมากขึ้น ในบทความนี้ เราจะมาพูดถึง Bubble Sort ซึ่งเป็นอัลกอริธึมที่ได้รับความนิยมแม้ว่าจะมีประสิทธิภาพต่ำเมื่อเปรียบเทียบกับอัลกอริธึมอื่น ๆ แต่ Bubble Sort ก็ยังคงมีความสำคัญในด้านการศึกษา และการสอนพื้นฐานการเขียนโปรแกรม

 

Bubble Sort คืออะไร?

Bubble Sort เป็นอัลกอริธึมการเรียงลำดับที่ทำงานด้วยวิธีการเปรียบเทียบค่าระหว่างคู่ขององค์ประกอบในลิสต์ (list) และสลับตำแหน่งหากพบว่าค่าตัวที่มากกว่าอยู่ก่อนค่าตัวที่น้อยกว่า โดยกระบวนการนี้จะทำซ้ำไปเรื่อย ๆ จนกว่าลิสต์จะถูกเรียงลำดับอย่างสมบูรณ์

ตัวอย่างการทำงานของ Bubble Sort

สมมุติว่าเรามีลิสต์ของตัวเลขที่ไม่เรียงลำดับ [5, 2, 9, 1, 5, 6] การทำงานของ Bubble Sort จะเป็นดังนี้:

1. เปรียบเทียบ 5 และ 2 → สลับกัน → [2, 5, 9, 1, 5, 6]

2. เปรียบเทียบ 5 และ 9 → ไม่ต้องสลับ → [2, 5, 9, 1, 5, 6]

3. เปรียบเทียบ 9 และ 1 → สลับกัน → [2, 5, 1, 9, 5, 6]

4. เปรียบเทียบ 9 และ 5 → สลับกัน → [2, 5, 1, 5, 9, 6]

5. เปรียบเทียบ 9 และ 6 → สลับกัน → [2, 5, 1, 5, 6, 9]

ทำไปเรื่อย ๆ จะพบว่า เมื่อไม่มีการสลับเกิดขึ้นอีก แสดงว่าลิสต์ได้ถูกเรียงลำดับแล้ว

 

ตัวอย่างโค้ด Bubble Sort ด้วยภาษา Kotlin

มาลองดูโค้ดของ Bubble Sort กันว่าเขียนยังไงในภาษา Kotlin:

 fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1) {
        var swapped = false
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j+1]
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
                swapped = true
            }
        }
        // If no two elements were swapped by inner loop, then break
        if (!swapped) {
            break
        }
    }
}

fun main() {
    val arr = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    bubbleSort(arr)
    println("Sorted array: ${arr.joinToString(", ")}")
}

ในโค้ดด้านบน ฟังก์ชัน `bubbleSort` จะทำการเรียงลำดับค่าต่าง ๆ ในอาร์เรย์ `arr` โดยการทำซ้ำเพื่อเปรียบเทียบและสลับองค์ประกอบตามที่อธิบายไปแล้ว

 

Use Case ในโลกจริง

Bubble Sort มักจะถูกใช้ในสถานการณ์การศึกษาเพื่อสอนหลักการเบื้องต้นของการเขียนอัลกอริธึมและการใช้งานลูป (loop) ตัวอย่างเช่น อาจใช้ให้สถาบันการศึกษาใช้ Bubble Sort ในการจัดเรียงคะแนนของนักเรียนหรือจัดเรียงข้อมูลในรายการสั่งซื้อผลิตภัณฑ์ อย่างไรก็ตาม ด้วยความช้าเมื่อจำนวนข้อมูลมากขึ้น ทำให้อัลกอริธึมนี้ไม่แนะนำในการใช้งานจริงที่ต้องการประสิทธิภาพสูง

 

วิเคราะห์ Complexity ของ Bubble Sort

Time Complexity

- Worst-case: O(n^2) เมื่ออาร์เรย์ถูกจัดเรียงในลำดับที่ตรงข้าม - Average-case: O(n^2) - Best-case: O(n) โดยกรณีเมื่ออาร์เรย์เรียงพร้อม

Space Complexity

- O(1) เนื่องจาก Bubble Sort เป็นอัลกอริธึมที่ทำการเรียงลำดับแบบ in-place ไม่ต้องการใช้หน่วยความจำเพิ่มเติมนอกจากตัวแปรชั่วคราว

 

ข้อดีและข้อเสียของ Bubble Sort

ข้อดี

- เข้าใจง่าย: Easy to understand, making it a good starting point for beginners - ทำงานใน memory ที่จำกัด: Consumes less memory than other sorting algorithms as it doesn’t require additional storage

ข้อเสีย

- ความเร็ว: O(n^2) time complexity makes it impractical for large datasets - ไม่เหมาะสำหรับใช้ในงานจริง: Bubble Sort is generally not used in real-world applications due to inefficiency when dealing with large amounts of data

 

สรุป

Bubble Sort อาจไม่ได้เป็นอัลกอริธึมที่มีประสิทธิภาพสูงที่สุด แต่การเรียนรู้และเข้าใจ Bubble Sort สามารถช่วยให้ผู้เรียนพัฒนาทักษะการคิดเชิงตรรกะและทำความเข้าใจกับอัลกอริธึมขั้นสูงอื่น ๆ ในอนาคตได้ง่ายขึ้น หากคุณต้องการเรียนรู้เพิ่มเติมเกี่ยวกับการเขียนโปรแกรมและอัลกอริธึมต่าง ๆ ไม่ว่าจะเป็น Bubble Sort หรืออัลกอริธึมอื่น ๆ มาเรียนกับเราที่ EPT (Expert-Programming-Tutor) เรามีคอร์สและเนื้อหาที่เตรียมไว้เพื่อช่วยให้คุณเป็นนักพัฒนาที่เชี่ยวชาญได้ในไม่ช้า!

 

 

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง