Gelembung semacam Jawa

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]

Seberapa efisien bubble sort?

Bubble sort adalah salah satu algoritma termudah untuk diimplementasikan tetapi tidak efisien. Ini membutuhkan sepasang loop bersarang. Bahkan dalam versi algoritme yang dioptimalkan dalam kasus terburuk (setiap elemen kumpulan data dalam urutan terbalik ke yang diinginkan) loop luar berulang sekali untuk setiap n elemen kumpulan data. Perulangan dalam berulang n kali untuk yang pertama kali, ( n-1 ) untuk yang kedua, dan seterusnya. Oleh karena itu, untuk mendapatkan semua n , elemen diurutkan, loop harus dieksekusi n*(n-1)/2 kali. Ini memanggil O(n ² )kompleksitas waktu dan berarti bahwa algoritma melakukan sekitar 500.000 perbandingan untuk 1.000 elemen array. Namun, algoritme bubble sort cukup efektif dalam penggunaan memori (kompleksitas memori adalah O(n) ) dan sangat bagus untuk kumpulan data kecil yang hampir terurut.