Algoritma Susun Gelembung

Dalam tutorial ini, anda akan belajar bagaimana penyusun gelembung berfungsi. Anda juga akan dapati contoh-contoh yang berfungsi seperti jenis gelembung di C, C ++, Java dan Python.

Bubble sort adalah algoritma yang membandingkan elemen bersebelahan dan menukar kedudukannya jika tidak mengikut urutan yang dimaksudkan. Urutan boleh menaik atau menurun.

Bagaimana Bubble Sort Berfungsi?

Bermula dari indeks pertama, bandingkan elemen pertama dan kedua. Sekiranya elemen pertama lebih besar daripada elemen kedua, elemen tersebut ditukar.
Sekarang, bandingkan elemen kedua dan ketiga. Tukar mereka jika tidak teratur.
Proses di atas berterusan sehingga elemen terakhir. Bandingkan unsur bersebelahan
Proses yang sama berlaku untuk lelaran yang tinggal. Selepas setiap lelaran, elemen terbesar di antara unsur yang tidak disusun diletakkan di hujungnya.
Dalam setiap lelaran, perbandingan berlaku hingga elemen terakhir yang tidak disusun.
Susunan disusun apabila semua elemen yang tidak disusun diletakkan pada kedudukan yang betul. Bandingkan unsur bersebelahan Bandingkan unsur bersebelahan Bandingkan unsur bersebelahan

Algoritma Susun Gelembung

 bubbleSort (array) untuk i rightElement swap leftElement dan rightElement end bubbleSort

Contoh Python, Java dan C / C ++

Python Java C C ++

 # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)

 // Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j  to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )

 // Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Susun Gelembung Dioptimumkan

Dalam kod di atas, semua kemungkinan perbandingan dibuat walaupun susunan sudah disusun. Ini meningkatkan masa pelaksanaan.

Kod tersebut dapat dioptimumkan dengan memperkenalkan pemboleh ubah tambahan yang ditukar. Selepas setiap lelaran, jika tidak ada pertukaran berlaku, tidak perlu melakukan gelung lebih lanjut.

Dalam kes seperti itu, pemboleh ubah bertukar menjadi salah. Oleh itu, kita dapat mengelakkan lelaran selanjutnya.

Algoritma untuk pengumpulan gelembung yang dioptimumkan adalah

 bubbleSort (array) ditukar <- false untuk i rightElemen swap kiriElemen dan kananElemen ditukar <- true end bubbleSort

Contoh Susunan Gelembung Dioptimumkan

Python Java C C +

 # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)

 // Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j  to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )

 // Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (

  // Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Kerumitan

Bubble Sort adalah salah satu algoritma penyusun paling mudah. Dua gelung dilaksanakan dalam algoritma.

Kitaran	Bilangan Perbandingan
1hb	(n-1)
Ke-2	(n-2)
Ke-3	(n-3)
….	…
terakhir	1

Bilangan perbandingan: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 hampir sama dengan n ²

Kerumitan: O (n ² )

Kita juga dapat menganalisis kerumitan dengan hanya memerhatikan bilangan gelung. Terdapat 2 gelung sehingga kerumitannyan*n = n²

Kerumitan Masa:

Kerumitan Kes Terburuk: Sekiranya kita mahu menyusun mengikut tertib menaik dan susunannya berada dalam urutan menurun maka, kes terburuk berlaku.O(n²)
Kerumitan Kes Terbaik:O(n)
Sekiranya susunan sudah disusun, maka tidak perlu disusun.
Kerumitan Kes Rata-rata: Ia berlaku apabila unsur-unsur array berada dalam urutan yang tidak rata (tidak menaik atau menurun)O(n²)