อัลกอริทึมการเรียงลำดับแบบฟองสบู่ใน C, Java และ Python

อินฟอร์เมเทค ดิจิตอล » อัลกอริทึม » อัลกอริทึมการเรียงลำดับแบบฟองสบู่ใน C, Java และ Python

อัลกอริทึมการเรียงลำดับแบบฟองอากาศเป็นหนึ่งในอัลกอริทึมที่ง่ายที่สุดและพื้นฐานที่สุดที่ใช้ในการเรียงลำดับองค์ประกอบในรายการ ความเรียบง่ายทำให้เป็นตัวเลือกที่ยอดเยี่ยมสำหรับการทำความเข้าใจแนวคิดพื้นฐานของอัลกอริทึมการเรียงลำดับ อัลกอริทึมนี้มักใช้ในแอปพลิเคชันและโปรแกรมที่มีจำนวนองค์ประกอบที่ต้องเรียงลำดับน้อย

ในบทความนี้ เราจะมุ่งเน้นไปที่การนำอัลกอริทึมการเรียงลำดับแบบบับเบิลซอร์ตไปใช้ในสองภาษาโปรแกรมยอดนิยม ได้แก่ C และ Java เราจะสำรวจขั้นตอนที่จำเป็นในการนำอัลกอริทึมนี้ไปใช้ในแต่ละภาษา โดยวิเคราะห์ซอร์สโค้ดและให้คำอธิบายโดยละเอียด

อัลกอริทึมการเรียงลำดับแบบฟองสบู่ใน C และ Java

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

อัลกอริทึมการเรียงลำดับแบบฟองอากาศทำงานอย่างไรใน C และ Java?

อัลกอริธึมการเรียงลำดับแบบฟองเป็นวิธีการเรียงลำดับองค์ประกอบที่เรียบง่ายแต่มีประสิทธิภาพ การทำงานทั่วไปของอัลกอริทึมแสดงไว้ด้านล่างนี้:

1. เราเริ่มต้นด้วยรายการของสิ่งที่ไม่ได้จัดลำดับ
2. เราทำซ้ำผ่านรายการโดยเปรียบเทียบองค์ประกอบที่อยู่ติดกันแต่ละคู่
3. หากองค์ประกอบอยู่ในลำดับที่ไม่ถูกต้องเราจะสลับกัน
4. เราดำเนินการวนซ้ำในรายการต่อไปจนกระทั่งมีการเรียงลำดับครบถ้วน
5. ขั้นตอนการวนซ้ำจะทำซ้ำตามจำนวนครั้งที่จำเป็น จนกระทั่งไม่มีการสลับใดๆ เกิดขึ้นอีกในครั้งเดียว

การนำอัลกอริธึมการเรียงลำดับแบบฟองสบู่ไปใช้ในภาษา C

ด้านล่างนี้คือตัวอย่างการใช้งานอัลกอริทึมการเรียงลำดับแบบบับเบิลซอร์ตในภาษาซี :

#include <stdio.h>

void bubbleSort(int array[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

int main() {
    int array[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(array) / sizeof(array[0]);
    bubbleSort(array, size);
    printf("Array ordenado: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    return 0;
}

ในโค้ดอัลกอริทึมฟองนี้ เราได้กำหนดฟังก์ชันที่เรียกว่า bubbleSort ซึ่งรับอาร์เรย์และขนาดของมันเป็นพารามิเตอร์ ฟังก์ชั่นนี้ดำเนินการอัลกอริทึมการเรียงลำดับแบบฟองสบู่โดยใช้สองลูป for- ลูปแรก for วนซ้ำองค์ประกอบของอาร์เรย์และลูปที่สอง for ทำการเปรียบเทียบและแลกเปลี่ยนตามความจำเป็น

สุดท้ายในฟังก์ชั่น mainเราได้สร้างตัวอย่างอาร์เรย์และคำนวณขนาดของมัน จากนั้นเราจะเรียกใช้ฟังก์ชัน bubbleSort การส่งอาร์เรย์และขนาดของมันเป็นอาร์กิวเมนต์ ในที่สุดเราจะพิมพ์อาร์เรย์ที่เรียงลำดับแล้วออกสู่หน้าจอ

การนำอัลกอริธึมการเรียงลำดับแบบฟองสบู่ไปใช้ใน Java

ด้านล่างนี้เราจะนำเสนอการใช้งานอัลกอริทึมการเรียงลำดับแบบฟองสบู่ในภาษา Java:

import java.util.Arrays;

public class BubbleSort {
    public static void bubbleSort(int[] array) {
        int size = array.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(array);
        System.out.println("Array ordenado: " + Arrays.toString(array));
    }
}

ในโค้ดนี้เราได้กำหนดคลาสที่เรียกว่า BubbleSort- ภายในคลาสนี้เราได้ประกาศเมธอดคงที่ที่เรียกว่า bubbleSort ซึ่งรับเอาอาร์เรย์เป็นพารามิเตอร์ วิธีการ bubbleSort ดำเนินการอัลกอริทึมการเรียงลำดับฟองสบู่โดยใช้สองลูป forเช่นเดียวกับในการใช้งาน C

ในวิธีการ mainเราได้สร้างตัวอย่างอาร์เรย์และเรียกใช้เมธอด bubbleSort การส่งผ่านอาร์เรย์เป็นอาร์กิวเมนต์ สุดท้ายเราใช้ Arrays.toString(array) เพื่อพิมพ์อาร์เรย์ที่เรียงลำดับแล้วไปยังคอนโซล

การนำอัลกอริธึมการเรียงลำดับแบบฟองสบู่ไปใช้ใน Python

เทียบเท่ากับอัลกอริทึมการเรียงลำดับฟองสบู่ของ Python:

def bubble_sort(array):
    size = len(array)
    for i in range(size - 1):
        for j in range(size - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]

array = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(array)
print("Array ordenado:", array)

 

ข้อดีของอัลกอริธึมการเรียงลำดับแบบฟองสบู่

อัลกอริธึมการเรียงลำดับแบบฟองสบู่มีข้อดีบางประการ เช่น:

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

ข้อเสียของอัลกอริธึมการเรียงลำดับแบบฟองสบู่

แม้ว่าจะดูเรียบง่าย แต่อัลกอริทึมการเรียงลำดับแบบฟองก็มีข้อเสียบางประการด้วยเช่นกัน:

1. ความไม่มีประสิทธิภาพในชุดข้อมูลขนาดใหญ่:อัลกอริทึมการเรียงลำดับแบบฟองอากาศไม่มีประสิทธิภาพในแง่ของเวลาในการดำเนินการเมื่อจัดการกับชุดข้อมูลขนาดใหญ่ ความซับซ้อนของเวลาคือ O(n^2) ซึ่งหมายถึงเวลาในการดำเนินการเพิ่มขึ้นอย่างรวดเร็วเมื่อขนาดของชุดข้อมูลเพิ่มขึ้น
2. จำนวนการเปรียบเทียบ:อัลกอริทึมการเรียงลำดับแบบฟองจะดำเนินการเปรียบเทียบจำนวนมาก แม้ว่าอาร์เรย์จะได้รับการเรียงลำดับแล้วก็ตาม ซึ่งอาจนำไปสู่การสูญเสียประสิทธิภาพและทรัพยากรที่ไม่จำเป็น

ทางเลือกอื่นสำหรับอัลกอริธึมการเรียงลำดับแบบฟองสบู่

เมื่อชุดข้อมูลมีขนาดใหญ่และซับซ้อนมากขึ้น จึงควรพิจารณาทางเลือกที่มีประสิทธิภาพมากกว่าสำหรับอัลกอริทึมการเรียงลำดับแบบฟองสบู่ ทางเลือกยอดนิยมบางส่วนได้แก่:

1. อัลกอริทึมการเรียงลำดับแบบแทรก:อัลกอริทึมนี้จะแบ่งรายการออกเป็นส่วนที่มีลำดับและส่วนที่มีลำดับ และแทรกแต่ละองค์ประกอบของส่วนที่มีลำดับเข้าไปในตำแหน่งที่ถูกต้องภายในส่วนที่มีลำดับนั้น ในกรณีที่เลวร้ายที่สุด จะมีความซับซ้อนของเวลาเท่ากับ O(n^2) แต่ในกรณีส่วนใหญ่ มีประสิทธิภาพมากกว่าอัลกอริทึมการเรียงลำดับแบบฟองสบู่
2. อัลกอริทึมการเรียงลำดับการเลือก:อัลกอริทึมนี้จะแบ่งรายการออกเป็นส่วนที่มีลำดับและส่วนที่มีลำดับ และเลือกองค์ประกอบที่เล็กที่สุดจากส่วนที่ไม่มีลำดับซ้ำๆ และวางไว้ที่ตอนท้ายของส่วนที่มีลำดับ ในกรณีเลวร้ายจะมีความซับซ้อนของเวลาเท่ากับ O(n^2) แต่ยังมีประสิทธิภาพมากกว่าอัลกอริทึมการเรียงลำดับแบบฟองสบู่ในกรณีส่วนใหญ่อีกด้วย

คำถามที่พบบ่อยเกี่ยวกับอัลกอริทึมฟองสบู่

1. ความซับซ้อนของเวลาของอัลกอริทึมการเรียงลำดับแบบฟองสบู่คืออะไร

อัลกอริทึมการเรียงลำดับแบบฟองสบู่มีความซับซ้อนของเวลาเท่ากับ O(n^2) โดยที่ "n" คือจำนวนขององค์ประกอบที่ต้องเรียงลำดับ ซึ่งหมายความว่าเวลาในการทำงานของอัลกอริทึมจะเพิ่มขึ้นแบบกำลังสองเมื่อขนาดของรายการเพิ่มขึ้น

2. เมื่อใดจึงเหมาะสมที่จะใช้อัลกอริทึมการเรียงลำดับแบบฟองสบู่?

อัลกอริทึมการเรียงลำดับแบบฟองอากาศเหมาะเมื่อรายการองค์ประกอบที่ต้องเรียงลำดับมีจำนวนน้อย เนื่องจากความซับซ้อนของเวลา จึงไม่แนะนำให้ใช้กับชุดข้อมูลขนาดใหญ่ เนื่องจากมีอัลกอริทึมที่มีประสิทธิภาพมากกว่าอยู่แล้ว

3. อัลกอริธึมการเรียงลำดับแบบฟองสบู่มีเสถียรภาพหรือไม่?

ใช่ อัลกอริธึมการเรียงลำดับแบบฟองสบู่เป็นอัลกอริธึมการเรียงลำดับที่มีเสถียรภาพ ซึ่งหมายความว่าจะรักษาลำดับสัมพันธ์ขององค์ประกอบด้วยคีย์เท่ากันในระหว่างกระบวนการเรียงลำดับ

4. ทางเลือกที่ดีที่สุดสำหรับอัลกอริทึมการเรียงลำดับแบบฟองอากาศคืออะไร?

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

5. อัลกอริทึมการเรียงลำดับแบบฟองอากาศสามารถปรับปรุงได้หรือไม่

ใช่ มีรูปแบบและการปรับแต่งของอัลกอริทึมการเรียงลำดับแบบฟอง เช่น "การเรียงลำดับแบบฟองสองทิศทาง" และ "การเรียงลำดับแบบฟองที่ปรับปรุงแล้ว" การเพิ่มประสิทธิภาพเหล่านี้ช่วยลดจำนวนการเปรียบเทียบและจำนวนการวนซ้ำที่จำเป็นในการเรียงลำดับรายการ

6. ฉันสามารถหาข้อมูลเพิ่มเติมเกี่ยวกับอัลกอริทึมการเรียงลำดับได้จากที่ไหน

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

• อัลกอริทึมการเรียงลำดับในวิกิพีเดีย
• การเรียงลำดับแบบฟองสบู่บน Wikipedia

ข้อสรุป

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

แม้ว่าอัลกอริทึมการเรียงลำดับแบบฟองสบู่จะเรียบง่ายและนำไปใช้งานได้ง่าย แต่สิ่งสำคัญคือต้องพิจารณาถึงประสิทธิภาพของมันเมื่อใช้กับชุดข้อมูลขนาดใหญ่ ในกรณีเช่นนี้ ขอแนะนำให้พิจารณาใช้อัลกอริธึมการเรียงลำดับที่มีประสิทธิภาพมากกว่า เช่น การเรียงลำดับแบบแทรกหรือการเรียงลำดับแบบเลือก

เราหวังว่าบทความนี้จะทำให้คุณเข้าใจอัลกอริธึมการเรียงลำดับแบบฟองได้ดียิ่งขึ้น