Bubble Sort di Java

1. Perkenalan

Dalam artikel singkat ini, kita akan mempelajari algoritme Bubble Sort secara detail, dengan fokus pada implementasi Java.

Ini adalah salah satu algoritme pengurutan yang paling mudah; Ide intinya adalah untuk terus menukar elemen yang berdekatan dari sebuah larik jika mereka berada dalam urutan yang salah hingga koleksi diurutkan.

Item kecil "menggelembung" ke bagian atas daftar saat kami mengulang struktur data. Oleh karena itu, teknik ini dikenal dengan istilah bubble sort.

Karena pengurutan dilakukan dengan menukar, kita dapat mengatakan itu melakukan pengurutan di tempat.

Selain itu, jika dua elemen memiliki nilai yang sama, urutan data yang dihasilkan akan dipertahankan - yang membuatnya menjadi pengurutan yang stabil.

2. Metodologi

Seperti yang disebutkan sebelumnya, untuk mengurutkan larik, kami mengulanginya sambil membandingkan elemen yang berdekatan, dan menukarnya jika perlu. Untuk larik berukuran n , kami melakukan n-1 iterasi seperti itu.

Mari kita ambil contoh untuk memahami metodologi. Kami ingin mengurutkan array dalam urutan menaik:

4 2 1 6 3 5

Kami memulai iterasi pertama dengan membandingkan 4 dan 2; mereka pasti tidak dalam urutan yang benar. Pertukaran akan menghasilkan:

[2 4] 1 6 3 5

Sekarang, ulangi hal yang sama untuk 4 dan 1:

2 [1 4] 6 3 5

Kami terus melakukannya sampai akhir:

2 1 [ 4 6] 3 5

2 1 4 [3 6] 5

2 1 4 3 [5 6]

Seperti yang bisa kita lihat, di akhir iterasi pertama, kita mendapatkan elemen terakhir di tempat yang semestinya. Sekarang, yang perlu kita lakukan adalah mengulangi prosedur yang sama di iterasi lebih lanjut. Kecuali, kami mengecualikan elemen yang sudah diurutkan.

Pada iterasi kedua, kita akan melakukan iterasi melalui seluruh array kecuali elemen terakhir. Demikian pula, untuk iterasi ke-3, kami menghilangkan 2 elemen terakhir. Secara umum, untuk iterasi ke-k, kita melakukan iterasi hingga indeks nk (tidak termasuk). Di akhir iterasi n-1 , kita akan mendapatkan array yang diurutkan.

Sekarang setelah Anda memahami tekniknya, mari selami penerapannya.

3. Implementasi

Mari menerapkan pengurutan untuk larik contoh yang kita diskusikan menggunakan pendekatan Java 8:

void bubbleSort(Integer[] arr) { int n = arr.length; IntStream.range(0, n - 1) .flatMap(i -> IntStream.range(1, n - i)) .forEach(j -> { if (arr[j - 1] > arr[j]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } }); }

Dan tes JUnit cepat untuk algoritme:

@Test public void whenSortedWithBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.bubbleSort(array); assertArrayEquals(array, sortedArray); }

4. Kompleksitas dan Optimasi

Seperti yang dapat kita lihat, untuk rata-rata dan kasus terburuk , kompleksitas waktu adalah O (n ^ 2) .

Selain itu, kompleksitas ruang , bahkan dalam skenario terburuk, adalah O (1) karena algoritme Bubble sort tidak memerlukan memori tambahan dan pengurutan dilakukan dalam larik asli.

Dengan menganalisis solusi secara cermat, kita dapat melihat bahwa jika tidak ada swap yang ditemukan dalam sebuah iterasi, kita tidak perlu melakukan iterasi lebih lanjut .

Dalam kasus contoh yang dibahas sebelumnya, setelah iterasi ke-2, kita mendapatkan:

1 2 3 4 5 6

Pada iterasi ketiga, kita tidak perlu menukar pasangan elemen yang berdekatan. Jadi kita bisa melewati semua iterasi yang tersisa.

In case of a sorted array, swapping won't be needed in the first iteration itself – which means we can stop the execution. This is the best case scenario and the time complexity of the algorithm is O(n).

Now, let's implement the optimized solution.

public void optimizedBubbleSort(Integer[] arr) { int i = 0, n = arr.length; boolean swapNeeded = true; while (i < n - 1 && swapNeeded) { swapNeeded = false; for (int j = 1; j  arr[j]) { int temp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = temp; swapNeeded = true; } } if(!swapNeeded) { break; } i++; } }

Let's check the output for the optimized algorithm:

@Test public void givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.optimizedBubbleSort(array); assertArrayEquals(array, sortedArray); }

5. Conclusion

In this tutorial, we saw how Bubble Sort works, and it's implementation in Java. We also saw how it can be optimized. To summarize, it's an in-place stable algorithm, with time complexity:

  • Worst and Average case: O(n*n), when the array is in reverse order
  • Best case: O(n), when the array is already sorted

Algoritma ini populer dalam grafik komputer, karena kemampuannya untuk mendeteksi beberapa kesalahan kecil dalam penyortiran. Misalnya, dalam larik yang hampir terurut, hanya dua elemen yang perlu ditukar, untuk mendapatkan larik yang diurutkan sepenuhnya. Bubble Sort dapat memperbaiki kesalahan seperti itu (yaitu, mengurutkan larik ini) dalam waktu linier.

Seperti biasa, kode untuk implementasi algoritma ini dapat ditemukan di GitHub.