Jika Anda pernah mendengar metode pengurutan dalam pemrograman, kemungkinan besar itu adalah algoritma pengurutan gelembung. Ini adalah salah satu yang terkenal. Setiap programmer mengetahui bubble sort (atau setidaknya mendengarnya saat belajar) bukan karena ini adalah algoritma pengurutan terbaik di dunia, tetapi yang paling mudah. Algoritme ini biasanya digunakan untuk tujuan pembelajaran atau Anda mungkin mendapatkannya sebagai tugas di Wawancara Java Junior Anda. Algoritma Java Bubble sort sangat mudah dipahami, namun tidak efisien. Bagaimanapun, mari kita cari tahu.
Apa itu menyortir
Pertama-tama, Anda perlu memahami apa itu pengurutan secara umum dan apa yang bisa kita urutkan dalam program Java. Jika kita dapat membandingkan dua atau lebih elemen atau objek dengan salah satu atributnya, itu berarti mereka dapat diurutkan berdasarkan atribut ini. Misalnya, angka dalam urutan naik atau turun atau kata menurut abjad. Oleh karena itu, elemen harus sebanding satu sama lain. Omong-omong, unsur-unsur apa? Di Java, kita bisa membandingkan elemen Collections. Misalnya kita bisa mengurutkan Array atau ArrayList dari bilangan bulat, String dan sebagainya.Bagaimana cara kerja pengurutan gelembung
Katakanlah, kita perlu mengurutkan array bilangan bulat dalam urutan menaik, yaitu dari yang terkecil hingga yang terbesar. Pertama, kita menelusuri seluruh array dan membandingkan setiap 2 elemen yang berdekatan. Jika urutannya salah (tetangga kiri lebih besar dari yang kanan), kami menukarnya. Pada pass pertama di bagian akhir akan muncul elemen terbesar (jika kita mengurutkan secara menaik). Bisa dibilang, elemen terbesar “muncul”. Itulah alasan dari nama algoritma Bubble sort. Kami mengulangi langkah pertama dari elemen pertama ke elemen berikutnya hingga terakhir. Kami memiliki elemen terbesar kedua di tempat terakhir. Dan seterusnya. Kami dapat sedikit meningkatkan algoritme dengan memeriksa apakah setidaknya satu pertukaran pada langkah sebelumnya dilakukan. Jika tidak, kami menghentikan lari kami di sepanjang larik.Contoh pengurutan gelembung
Mari kita urutkan array bilangan bulat, satu, yang dapat Anda lihat di bawah pada gambar. Langkah 1: kita akan melalui array. Algoritme dimulai dengan dua elemen pertama (dengan indeks 0 dan 1), 8 dan 7, dan memeriksa apakah urutannya benar. Jelas, 8 > 7, jadi kami menukarnya. Selanjutnya, kami melihat elemen kedua dan ketiga (indeks 1 dan 2), sekarang ini adalah 8 dan 1. Untuk alasan yang sama, kami menukarnya. Untuk ketiga kalinya kami membandingkan 8 dan 2 dan, setidaknya 8 dan 5. Kami membuat total empat pertukaran: (8, 7), (8, 1), (8, 2) dan (8, 5). Nilai 8, yang terbesar dalam larik ini, muncul di akhir daftar ke posisi yang benar. Hasil dari langkah pertama kerja algoritma Bubble sort adalah array berikutnya: Langkah 2. Lakukan hal yang sama dengan (7,1), (7,2) dan (7,5). 7 sekarang berada di posisi kedua dari belakang, dan kita tidak perlu membandingkannya dengan "ekor" daftar, sudah diurutkan. Hasil dari langkah kedua algoritma Bubble sort bekerja adalah larik berikutnya: Seperti yang Anda lihat, larik ini sudah diurutkan. Pokoknya algoritma Bubble Sort harus berjalan setidaknya sekali lagi. Langkah3. Kami akan melalui array sekali lagi. Tidak ada yang perlu ditukar di sini, jadi jika kita menggunakan algoritme Bubble Sort yang "ditingkatkan" (dengan memeriksa apakah setidaknya satu pertukaran dilakukan pada langkah sebelumnya) langkah ini adalah yang terakhir.Bubble sort kode Java
Bubble sort realisasi Java
Mari buat dua metode untuk Bubble sort. Yang pertama, bubbleSort(int[] myArray) adalah bidang datar. Ini berjalan melalui array setiap saat. Yang kedua, OptimizeBubbleSort(int myArray[]) dioptimalkan dengan menghentikan algoritme jika loop dalam tidak menyebabkan pertukaran apa pun. Penghitung menunjukkan kepada Anda berapa banyak langkah yang Anda lakukan saat menyortir. Di sini kita mendapatkan realisasi Bubble sort Java:
import java.util.Arrays;
public class BubbleSortExample {
// Plane Bubble sort example
public static int[] bubbleSort(int[] myArray) {
int temp = 0; // temporary element for swapping
int counter = 0; // element to count quantity of steps
for (int i = 0; i < myArray.length; i++) {
counter = i + 1;
for (int j = 1; j < (myArray.length - i); j++) {
if (myArray[j - 1] > myArray[j]) {
// swap array’s elements using temporary element
temp = myArray[j - 1];
myArray[j - 1] = myArray[j];
myArray[j] = temp;
}
}
}
System.out.println("Steps quantity, non optimized = " + counter);
return myArray;
}
// An optimized version of Java Bubble Sorting
static int[] optimizedBubbleSort(int myArray[]) {
int temp;
boolean swapped;
int counter = 0; // element to count quantity of steps
for (int i = 0; i < myArray.length - 1; i++) {
counter = i + 1;
swapped = false;
for (int j = 0; j < myArray.length - i - 1; j++) {
// counter++;
if (myArray[j] > myArray[j + 1]) {
// swap arr[j] and arr[j+1]
temp = myArray[j];
myArray[j] = myArray[j + 1];
myArray[j + 1] = temp;
swapped = true;
}
} // counter = i;
// If there weren't elements to swap in inner loop, then break
if (swapped == false) {
break;
}
}
System.out.println("steps quantity, optimized = " + counter);
return myArray;
}
public static void main(String[] args) {
int arr[] = {8, 7, 1, 2, 5};
int arr1[] = {8, 7, 1, 2, 5};
System.out.println("Array arr Before Bubble Sort");
// we use java.util.Arrays toString method to print the array
System.out.println(Arrays.toString(arr));
System.out.println("Array arr After Bubble Sort");
System.out.println(Arrays.toString(bubbleSort(arr)));
System.out.println("Array arr1 Before Bubble Sort");
System.out.println(Arrays.toString(arr1));
System.out.println("Array arr1 After Optimized Bubble Sort");
System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
}
}
Hasil kerja algoritma Bubble sort Java:
Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]
GO TO FULL VERSION