- Algoritma mudah dan stabil yang menyusun dengan membandingkan dan menukar elemen bersebelahan, sesuai untuk asas pembelajaran.
- Kerumitannya ialah O(n^2), jadi ia tidak cekap pada set besar dan melakukan banyak perbandingan yang tidak perlu.
- Pelaksanaannya dalam C, Java, dan Python telah ditunjukkan; alternatif yang lebih cekap seperti quicksort dan mergesort wujud untuk set data yang lebih besar.
Algoritma isihan buih ialah salah satu algoritma paling mudah dan paling asas yang digunakan untuk mengisih elemen dalam senarai. Kesederhanaannya menjadikannya pilihan yang sangat baik untuk memahami konsep asas algoritma pengisihan. Algoritma ini biasanya digunakan dalam aplikasi dan program di mana bilangan elemen yang hendak diisih adalah kecil.
Dalam artikel ini, kami akan menumpukan pada pelaksanaan algoritma bubble sort dalam dua bahasa pengaturcaraan popular: C dan Java. Kami akan meneroka langkah-langkah yang diperlukan untuk melaksanakan algoritma ini dalam setiap bahasa ini, menganalisis kod sumber dan memberikan penjelasan terperinci.
Algoritma Isih Buih dalam C dan Java
Algoritma isihan gelembung, seperti namanya, berfungsi dengan membandingkan pasangan elemen bersebelahan dalam senarai dan melakukan swap jika ia berada dalam susunan yang salah. Proses ini diulang sehingga senarai diisih sepenuhnya.
Bagaimanakah algoritma isihan gelembung berfungsi dalam C dan Java?
Algoritma isihan gelembung mengikut pendekatan yang mudah tetapi berkesan untuk menyusun elemen. Operasi umum algoritma ditunjukkan di bawah:
- Kami mulakan dengan senarai item yang tidak teratur.
- Kami mengulangi senarai, membandingkan setiap pasangan elemen bersebelahan.
- Jika elemen berada dalam susunan yang salah, kami menukarnya.
- Kami meneruskan lelaran ke atas senarai sehingga ia diisih sepenuhnya.
- Proses lelaran diulang seberapa banyak kali yang perlu sehingga tiada lagi pertukaran dibuat dalam pas lengkap.
Pelaksanaan algoritma isihan gelembung dalam C
Di bawah, kami membentangkan pelaksanaan algoritma bubble sort dalam bahasa 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;
}
Dalam kod algoritma gelembung ini, kami telah menentukan fungsi yang dipanggil bubbleSort yang mengambil tatasusunan dan saiznya sebagai parameter. Fungsi ini melaksanakan algoritma isihan gelembung menggunakan dua gelung for. Gelung pertama for berulang ke atas elemen tatasusunan, dan gelung kedua for membuat perbandingan dan pertukaran yang diperlukan.
Akhirnya, dalam fungsi main, kami telah mencipta tatasusunan contoh dan mengira saiznya. Kemudian kita panggil fungsi itu bubbleSort melepasi tatasusunan dan saiznya sebagai hujah. Akhirnya, kami mencetak tatasusunan yang diisih ke skrin.
Pelaksanaan algoritma isihan gelembung dalam Java
Di bawah ini kami membentangkan pelaksanaan algoritma isihan gelembung dalam bahasa 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));
}
}
Dalam kod ini, kami telah menentukan kelas yang dipanggil BubbleSort. Di dalam kelas ini, kami telah mengisytiharkan kaedah statik yang dipanggil bubbleSort yang mengambil tatasusunan sebagai parameter. Kaedahnya bubbleSort melaksanakan algoritma isihan gelembung menggunakan dua gelung for, sama seperti dalam pelaksanaan C.
Dalam kaedah main, kami telah mencipta tatasusunan contoh dan memanggil kaedah bubbleSort melepasi tatasusunan sebagai hujah. Akhirnya, kita gunakan Arrays.toString(array) untuk mencetak tatasusunan yang diisih ke konsol.
Melaksanakan algoritma isihan gelembung dalam Python
Setara dengan algoritma jenis gelembung 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)
Kelebihan algoritma isihan gelembung
Algoritma isihan gelembung mempunyai beberapa kelebihan, seperti:
- Kesederhanaan: Algoritma isihan gelembung mudah difahami dan dilaksanakan. Ia tidak memerlukan pengetahuan yang rumit dan sesuai untuk pemula dalam pengaturcaraan.
- Kerumitan kod rendah: Kod yang diperlukan untuk melaksanakan algoritma isihan gelembung adalah agak pendek dan padat. Ini menjadikannya pilihan pantas untuk mengisih sebilangan kecil item.
Kelemahan algoritma isihan gelembung
Walaupun kesederhanaannya, algoritma isihan gelembung juga mempunyai beberapa kelemahan:
- Ketidakcekapan dalam set data yang besar: Algoritma isihan buih tidak cekap dari segi masa pelaksanaan apabila berurusan dengan set data yang besar. Kerumitan masanya ialah O(n^2), yang bermaksud bahawa masa pelaksanaan meningkat dengan cepat apabila saiz set data bertambah.
- Bilangan perbandingan: Algoritma isihan gelembung melakukan sejumlah besar perbandingan, walaupun apabila tatasusunan sudah diisih. Ini boleh menyebabkan kehilangan prestasi dan sumber yang tidak perlu.
Alternatif kepada algoritma isihan gelembung
Apabila set data menjadi lebih besar dan lebih kompleks, adalah penting untuk mempertimbangkan alternatif yang lebih cekap kepada algoritma isihan gelembung. Beberapa alternatif yang popular termasuk:
- Algoritma isihan sisipan: Algoritma ini membahagikan senarai kepada bahagian tertib dan bahagian tak tertib, dan memasukkan setiap elemen bahagian tak tertib ke kedudukan yang betul dalam bahagian tersusun. Ia mempunyai kerumitan masa O(n^2) dalam kes yang paling teruk, tetapi lebih cekap daripada algoritma isihan gelembung dalam kebanyakan kes.
- Algoritma Isih Pemilihan: Algoritma ini membahagikan senarai kepada bahagian tersusun dan bahagian yang tidak tersusun, dan berulang kali memilih elemen terkecil daripada bahagian yang tidak tersusun dan meletakkannya di hujung bahagian yang dipesan. Ia mempunyai kerumitan masa O(n^2) dalam kes terburuk, tetapi juga lebih cekap daripada algoritma isihan gelembung dalam kebanyakan kes.
Soalan Lazim Algoritma Buih
1. Apakah kerumitan masa algoritma isihan gelembung?
Algoritma isihan gelembung mempunyai kerumitan masa O(n^2), dengan “n” ialah bilangan elemen yang hendak diisih. Ini bermakna bahawa masa berjalan algoritma meningkat secara kuadratik apabila saiz senarai bertambah.
2. Bilakah sesuai untuk menggunakan algoritma isihan gelembung?
Algoritma isihan gelembung sesuai apabila senarai elemen yang hendak diisih adalah kecil. Oleh kerana kerumitan masanya, ia tidak disyorkan untuk digunakan pada set data yang besar kerana algoritma yang lebih cekap tersedia.
3. Adakah algoritma isihan gelembung stabil?
Ya, algoritma isihan gelembung ialah algoritma isihan yang stabil. Ini bermakna ia mengekalkan susunan relatif elemen dengan kunci yang sama semasa proses pengisihan.
4. Apakah alternatif terbaik kepada algoritma isihan gelembung?
Pemilihan alternatif terbaik kepada algoritma isihan gelembung bergantung pada konteks dan keperluan khusus masalah. Walau bagaimanapun, beberapa algoritma yang lebih cekap, seperti quicksort dan mergesort , digunakan secara meluas kerana kerumitan masanya yang lebih rendah.
5. Bolehkah algoritma isihan gelembung diperbaiki?
Ya, terdapat variasi dan pengoptimuman algoritma isihan gelembung, seperti "isih gelembung dua arah" dan "isih gelembung yang dipertingkatkan". Pengoptimuman ini mengurangkan bilangan perbandingan dan bilangan lelaran yang diperlukan untuk mengisih senarai.
6. Di manakah saya boleh mendapatkan maklumat lanjut tentang algoritma pengisihan?
Anda boleh mendapatkan lebih banyak maklumat tentang menyusun algoritma dalam sumber yang boleh dipercayai seperti Wikipedia. Berikut adalah beberapa pautan yang berguna:
Kesimpulan
Dalam artikel ini, kami telah meneroka algoritma isihan gelembung dalam bahasa pengaturcaraan C dan Java. Kami telah mempelajari cara algoritma ini berfungsi langkah demi langkah, dan kami telah melihat pelaksanaan praktikalnya dalam kedua-dua bahasa. Kami juga telah membincangkan kebaikan dan keburukan algoritma isihan gelembung, dan meneroka alternatif yang lebih cekap.
Walaupun algoritma isihan gelembung adalah mudah dan mudah untuk dilaksanakan, adalah penting untuk mempertimbangkan kecekapannya pada set data yang lebih besar. Dalam kes sedemikian, adalah dinasihatkan untuk mempertimbangkan algoritma pengisihan yang lebih cekap, seperti isihan sisipan atau isihan pemilihan.
Kami berharap artikel ini telah memberi anda pemahaman yang kukuh tentang algoritma isihan gelembung.