Bubble sort Java

Jika anda pernah mendengar kaedah pengisihan dalam pengaturcaraan, kemungkinan besar ia adalah algoritma isihan gelembung. Ia adalah satu yang terkenal. Setiap pengaturcara mengetahui jenis gelembung (atau sekurang-kurangnya mendengarnya semasa belajar) bukan kerana ia adalah algoritma pengisihan terbaik di dunia, tetapi yang paling mudah. Algoritma ini biasanya digunakan untuk tujuan pembelajaran atau anda mungkin mendapatkannya sebagai tugas dalam Java Junior Interview anda. Algoritma isihan Bubble Java sangat mudah difahami, namun ia bukanlah algoritma yang cekap. Bagaimanapun, mari kita fikirkan.

Apa yang menyusun

Pertama sekali, anda perlu memahami apa itu pengisihan secara umum dan apa yang boleh kita isi dalam program Java. Jika kita boleh membandingkan dua atau lebih elemen atau objek dengan mana-mana atributnya, ini bermakna ia boleh diisih mengikut atribut ini. Contohnya, nombor dalam susunan menaik atau menurun atau perkataan mengikut abjad. Oleh itu, unsur-unsur mestilah setanding antara satu sama lain. By the way, unsur-unsur apa? Di Jawa, kita boleh membandingkan elemen Koleksi. Contohnya kita boleh mengisih Array atau ArrayList integer, Strings dan sebagainya.

Bagaimana jenis gelembung berfungsi

Katakan, kita perlu mengisih tatasusunan integer dalam tertib menaik, iaitu, daripada nombor terkecil kepada nombor terbesar. Mula-mula, kita akan mengikuti keseluruhan tatasusunan dan membandingkan setiap 2 elemen jiran. Jika mereka berada dalam susunan yang salah (jiran kiri lebih besar daripada yang kanan), kami menukar mereka. Pada hantaran pertama pada penghujung ia akan muncul elemen terbesar (jika kita mengisih dalam tertib menaik). Anda boleh berkata, elemen terbesar "muncul". Itulah sebab nama algoritma isihan Bubble. Kami mengulangi langkah pertama dari elemen pertama hingga seterusnya hingga terakhir. Kami mempunyai elemen kedua terbesar di tempat seterusnya hingga terakhir. Dan sebagainya. Kita boleh meningkatkan sedikit algoritma dengan menyemak sama ada sekurang-kurangnya satu pertukaran pada langkah sebelumnya telah dibuat. Jika tidak, kita berhenti berjalan di sepanjang array.

Contoh jenis gelembung

Mari kita susun tatasusunan integer, satu, anda boleh lihat di bawah pada gambar. Langkah 1: kita akan melalui tatasusunan. Algoritma bermula dengan dua elemen pertama (dengan indeks 0 dan 1), 8 dan 7, dan menyemak sama ada ia berada dalam susunan yang betul. Jelas sekali, 8 > 7, jadi kami menukarnya. Seterusnya, kita melihat elemen kedua dan ketiga (indeks 1 dan 2), kini ini adalah 8 dan 1. Atas sebab yang sama, kita menukarnya. Untuk kali ketiga kami membandingkan 8 dan 2 dan, sekurang-kurangnya 8 dan 5. Kami membuat empat pertukaran secara keseluruhan: (8, 7), (8, 1), (8, 2) dan (8, 5). Nilai 8, yang terbesar dalam tatasusunan ini, muncul di penghujung senarai ke kedudukan yang betul. Hasil daripada langkah pertama algoritma isihan Bubble adalah tatasusunan seterusnya: Langkah 2. Melakukan perkara yang sama dengan (7,1), (7,2) dan (7,5). 7 kini berada di kedudukan kedua terakhir, dan kita tidak perlu membandingkannya dengan "ekor" senarai, ia sudah disusun. Hasil daripada langkah kedua algoritma isihan Bubble adalah tatasusunan seterusnya: Seperti yang anda lihat, tatasusunan ini sudah diisih. Bagaimanapun, algoritma Bubble Sort harus berjalan sekurang-kurangnya sekali lagi. Langkah3. Kami akan melalui tatasusunan sekali lagi. Tiada apa-apa untuk ditukar di sini, jadi jika kami menggunakan algoritma Isih Buih "diperbaiki" (dengan menyemak sama ada sekurang-kurangnya satu pertukaran pada langkah sebelumnya telah dibuat) langkah ini adalah yang terakhir.

Bubble sort kod Java

Realisasi Java jenis buih

Mari kita cipta dua kaedah untuk isihan Bubble. Yang pertama, bubbleSort(int[] myArray) ialah satah. Ia berjalan melalui tatasusunan setiap kali. Yang kedua, optimizedBubbleSort(int myArray[]) dioptimumkan dengan menghentikan algoritma jika gelung dalaman tidak menyebabkan sebarang pertukaran. Kaunter menunjukkan kepada anda berapa banyak langkah yang anda lakukan semasa mengisih. Di sini kami mendapat realisasi Java jenis Bubble:

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 Java sort Bubble:

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]

Sejauh manakah kecekapan jenis gelembung?

Bubble sort ialah salah satu algoritma yang paling mudah untuk dilaksanakan tetapi ia tidak cekap. Ia memerlukan sepasang gelung bersarang. Walaupun dalam versi algoritma yang dioptimumkan dalam kes terburuk (setiap elemen set data adalah dalam susunan terbalik kepada yang dikehendaki) gelung luar berulang sekali untuk setiap elemen n set data. Gelung dalam berulang kali n kali pertama, ( n-1 ) untuk yang kedua, dan seterusnya. Oleh itu, untuk mendapatkan semua n , elemen diisih, gelung perlu dilaksanakan n*(n-1)/2 kali. Ia memanggil O(n ² )kerumitan masa dan bermakna algoritma melakukan kira-kira 500 000 perbandingan untuk 1000 elemen tatasusunan. Walau bagaimanapun, algoritma isihan gelembung cukup berkesan dalam penggunaan ingatan (kerumitan memori ialah O(n) ) dan sangat bagus untuk set data kecil yang hampir diisih.