Algoritma Bubble Sort

Dalam tutorial ini, Anda akan mempelajari cara kerja bubble sort. Juga, Anda akan menemukan contoh kerja dari bubble sort dalam C, C ++, Java dan Python.

Bubble sort adalah algoritme yang membandingkan elemen yang berdekatan dan menukar posisinya jika tidak dalam urutan yang diinginkan. Urutannya bisa naik atau turun.

Bagaimana Cara Kerja Bubble Sort?

Mulai dari indeks pertama, bandingkan elemen pertama dan kedua. Jika elemen pertama lebih besar dari elemen kedua, mereka ditukar.
Sekarang, bandingkan elemen kedua dan ketiga. Tukar mereka jika tidak berurutan.
Proses di atas berlangsung hingga elemen terakhir. Bandingkan elemen yang berdekatan
Proses yang sama berlangsung untuk iterasi yang tersisa. Setelah setiap iterasi, elemen terbesar di antara elemen yang tidak disortir ditempatkan di akhir.
Dalam setiap iterasi, perbandingan berlangsung hingga elemen tak disortir terakhir.
Larik diurutkan ketika semua elemen yang tidak diurutkan ditempatkan pada posisi yang benar. Bandingkan elemen yang berdekatan Bandingkan elemen yang berdekatan Bandingkan elemen yang berdekatan

Bubble Sort Algorithm

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

Contoh Python, Java dan C / C ++

Python Java 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); )

Bubble Sort yang Dioptimalkan

Dalam kode di atas, semua kemungkinan perbandingan dibuat bahkan jika array sudah diurutkan. Ini meningkatkan waktu eksekusi.

Kode dapat dioptimalkan dengan memasukkan variabel ekstra yang ditukar. Setelah setiap iterasi, jika tidak ada swapping yang terjadi, maka tidak perlu melakukan loop lebih lanjut.

Dalam kasus seperti itu, variabel yang ditukar disetel ke salah. Dengan demikian, kami dapat mencegah iterasi lebih lanjut.

Algoritma untuk pengurutan gelembung yang dioptimalkan adalah

 bubbleSort (array) swapped <- false for i rightElement swap leftElement dan rightElement ditukar <- true end bubbleSort

Contoh Bubble Sort yang Dioptimalkan

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); )

Kompleksitas

Bubble Sort is one of the simplest sorting algorithms. Two loops are implemented in the algorithm.

Cycle	Number of Comparisons
1st	(n-1)
2nd	(n-2)
3rd	(n-3)
… .	…
last	1

Number of comparisons: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2 nearly equals to n²

Complexity: O(n²)

Also, we can analyze the complexity by simply observing the number of loops. There are 2 loops so the complexity is n*n = n²

Time Complexities:

Worst Case Complexity:O(n²)
If we want to sort in ascending order and the array is in descending order then, the worst case occurs.
Best Case Complexity:O(n)
If the array is already sorted, then there is no need for sorting.
Average Case Complexity: Ini terjadi ketika elemen-elemen array berada dalam urutan campur aduk (tidak naik atau turun).O(n²)