Melaksanakan jenis gelembung dalam Java

Terdapat sejumlah besar algoritma pengisihan, kebanyakannya adalah sangat khusus dan dibangunkan untuk menyelesaikan pelbagai masalah yang sempit dan berfungsi dengan jenis data tertentu. Tetapi di antara semua kepelbagaian ini, algoritma yang paling mudah adalah jenis gelembung, yang boleh dilaksanakan dalam mana-mana bahasa pengaturcaraan. Walaupun kesederhanaannya, ia mendasari banyak algoritma yang agak kompleks. Satu lagi kelebihan yang sama penting ialah kesederhanaannya, dan, oleh itu, ia boleh diingati dan dilaksanakan serta-merta, tanpa mempunyai sebarang literatur tambahan di hadapan anda.

pengenalan

Keseluruhan Internet moden terdiri daripada sejumlah besar jenis struktur data yang dikumpul dalam pangkalan data. Mereka menyimpan semua jenis maklumat, daripada data peribadi pengguna kepada teras semantik sistem automatik yang sangat pintar. Tidak perlu dikatakan, pengisihan data memainkan peranan yang sangat penting dalam jumlah besar maklumat berstruktur ini. Pengisihan boleh menjadi langkah wajib sebelum mencari sebarang maklumat dalam pangkalan data, dan pengetahuan tentang algoritma pengisihan memainkan peranan yang sangat penting dalam pengaturcaraan.

Menyusun melalui mata mesin dan mata manusia

Mari bayangkan anda perlu mengisih 5 lajur yang berbeza ketinggian dalam tertib menaik. Lajur ini boleh bermaksud apa-apa jenis maklumat (harga saham, jalur lebar saluran komunikasi, dll.); anda boleh membentangkan beberapa versi tugasan anda sendiri untuk menjadikannya lebih jelas. Nah, sebagai contoh, kami akan menyusun Avengers mengikut ketinggian: Tidak seperti program komputer, pengisihan tidak akan menjadi sukar untuk anda, kerana anda dapat melihat keseluruhan gambar dan dengan serta-merta dapat mengetahui wira mana yang perlu dipindahkan ke mana agar pengisihan mengikut ketinggian dapat diselesaikan dengan jayanya. Anda mungkin sudah meneka bahawa untuk mengisih struktur data ini dalam tertib menaik, cuma tukar tempat Hulk dan Iron Man:

Selesai!

Dan ini akan menyelesaikan pengisihan dengan jayanya. Walau bagaimanapun, komputer, tidak seperti anda, agak bodoh dan tidak melihat keseluruhan struktur data secara keseluruhan. Program kawalannya hanya boleh membandingkan dua nilai pada satu masa. Untuk menyelesaikan masalah ini, dia perlu meletakkan dua nombor dalam ingatannya dan melakukan operasi perbandingan pada mereka, dan kemudian beralih kepada pasangan nombor lain, dan seterusnya sehingga semua data telah dianalisis. Oleh itu, sebarang algoritma pengisihan boleh dipermudahkan dalam bentuk tiga langkah:

• Bandingkan dua elemen;
• Tukar atau salin salah satu daripadanya;
• Pergi ke elemen seterusnya;

Algoritma yang berbeza boleh melaksanakan operasi ini dengan cara yang berbeza, tetapi kami akan meneruskan untuk mempertimbangkan cara pengisihan gelembung berfungsi.

Algoritma Isih Buih

Isih gelembung dianggap paling mudah, tetapi sebelum menerangkan algoritma ini, mari bayangkan bagaimana anda akan mengisih Avengers mengikut ketinggian jika anda boleh, seperti mesin, membandingkan hanya dua wira antara satu sama lain dalam satu tempoh masa. Kemungkinan besar, anda akan melakukan perkara berikut (paling optimum):

• Anda beralih ke elemen sifar tatasusunan kami (Black Widow);
• Bandingkan elemen sifar (Black Widow) dengan yang pertama (Hulk);
• Jika elemen pada kedudukan sifar lebih tinggi, anda menukarnya;
• Jika tidak, jika elemen pada kedudukan sifar adalah lebih kecil, anda meninggalkannya di tempatnya;
• Beralih ke kedudukan ke kanan dan ulangi perbandingan (bandingkan Hulk dengan Kapten)

Selepas anda meneliti keseluruhan senarai dalam satu laluan dengan algoritma sedemikian, pengisihan tidak akan selesai sepenuhnya. Tetapi sebaliknya, elemen terbesar dalam senarai akan dialihkan ke kedudukan paling kanan. Ini akan sentiasa berlaku, kerana sebaik sahaja anda menemui elemen terbesar, anda akan sentiasa menukar tempat sehingga anda mengalihkannya ke penghujung. Iaitu, sebaik sahaja program "mencari" Hulk dalam tatasusunan, ia akan menggerakkannya lebih jauh ke bahagian paling akhir senarai: Inilah sebabnya mengapa algoritma ini dipanggil jenis gelembung, kerana hasil daripada operasinya, elemen terbesar dalam senarai akan berada di bahagian paling atas tatasusunan, dan semua elemen yang lebih kecil akan dialihkan satu kedudukan ke kiri: Untuk melengkapkan isihan, anda perlu kembali ke permulaan tatasusunan dan ulangi lima langkah yang diterangkan di atas sekali lagi, sekali lagi bergerak dari kiri ke kanan, membandingkan dan menggerakkan elemen seperti yang diperlukan. Tetapi kali ini anda perlu menghentikan algoritma satu elemen sebelum penghujung tatasusunan, kerana kita sudah tahu bahawa elemen terbesar (Hulk) berada di kedudukan paling kanan: Jadi program mesti mempunyai dua gelung. Untuk lebih jelas, sebelum kita meneruskan untuk menyemak kod program, anda boleh melihat visualisasi cara isihan gelembung berfungsi di pautan ini: Visualisasi cara isihan gelembung berfungsi

Pelaksanaan jenis gelembung di Jawa

Untuk menunjukkan cara pengisihan berfungsi dalam Java, berikut ialah kod program:

• mencipta tatasusunan 5 elemen;
• memuat naik kebangkitan avengers ke dalamnya;
• memaparkan kandungan tatasusunan;
• melaksanakan jenis gelembung;
• memaparkan semula tatasusunan yang diisih.

Anda boleh melihat kod di bawah, malah memuat turunnya ke dalam IntelliJ IDE kegemaran anda. Ia akan dianalisis di bawah:

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

Walaupun terdapat ulasan terperinci dalam kod, kami memberikan penerangan tentang beberapa kaedah yang dibentangkan dalam program. Kaedah utama yang menjalankan kerja utama dalam program ini ditulis dalam kelas ArrayBubble. Kelas mengandungi pembina dan beberapa kaedah:

• into– kaedah memasukkan elemen ke dalam tatasusunan;
• printer– memaparkan kandungan tatasusunan baris demi baris;

• toSwap– menyusun semula elemen jika perlu. Untuk melakukan ini, pembolehubah sementara digunakan dummy, di mana nilai nombor pertama ditulis, dan sebagai ganti nombor pertama nilai daripada nombor kedua ditulis. Kandungan daripada pembolehubah sementara kemudiannya ditulis ke nombor kedua. Ini adalah teknik standard untuk menukar dua elemen;

  dan akhirnya kaedah utama:

• bubbleSorter– yang melakukan kerja utama dan mengisih data yang disimpan dalam tatasusunan, kami akan membentangkannya secara berasingan lagi:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

Di sini anda harus memberi perhatian kepada dua kaunter: luaran outdan dalaman in. Pembilang luaranout mula menghitung nilai dari penghujung tatasusunan dan secara beransur-ansur berkurangan satu dengan setiap hantaran baharu. outDengan setiap laluan baharu, pembolehubah dianjak lebih jauh ke kiri supaya tidak menjejaskan nilai yang telah diisih ke sebelah kanan tatasusunan. Kaunter dalamanin mula menghitung nilai dari permulaan tatasusunan dan secara beransur-ansur meningkat sebanyak satu pada setiap hantaran baharu. Peningkatan inberlaku sehingga ia mencapai out(elemen terakhir dianalisis dalam pas semasa). Gelung dalam inmembandingkan dua sel bersebelahan indan in+1. Jika innombor yang lebih besar disimpan dalam daripada in+1, maka kaedah itu dipanggil toSwap, yang menukar tempat kedua-dua nombor ini.

Kesimpulan

Algoritma isihan gelembung adalah salah satu yang paling perlahan. Jika tatasusunan terdiri daripada elemen N, maka perbandingan N-1 akan dilakukan pada hantaran pertama, N-2 pada hantaran kedua, kemudian N-3, dsb. Iaitu, jumlah bilangan hantaran akan dibuat: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Oleh itu, apabila menyusun, algoritma melakukan kira-kira 0.5x(N ^2) perbandingan. Untuk N = 5, bilangan perbandingan akan menjadi lebih kurang 10, untuk N = 10 bilangan perbandingan akan meningkat kepada 45. Oleh itu, apabila bilangan elemen meningkat, kerumitan pengisihan meningkat dengan ketara: Kelajuan algoritma dipengaruhi bukan sahaja oleh bilangan hantaran, tetapi juga oleh bilangan pilih atur yang perlu dibuat. Untuk data rawak, bilangan pilih atur purata (N^2) / 4, iaitu kira-kira separuh daripada bilangan hantaran. Walau bagaimanapun, dalam kes yang paling teruk, bilangan pilih atur juga boleh N^2 / 2 - ini berlaku jika data pada mulanya diisih dalam susunan terbalik. Walaupun fakta bahawa ini adalah algoritma pengisihan yang agak perlahan, adalah penting untuk mengetahui dan memahami cara ia berfungsi, dan, seperti yang dinyatakan sebelum ini, ia adalah asas untuk algoritma yang lebih kompleks. Jgd!