Menerapkan bubble sort di Java

Ada cukup banyak algoritma pengurutan, banyak di antaranya sangat spesifik dan dikembangkan untuk memecahkan masalah yang sempit dan bekerja dengan tipe data tertentu. Namun di antara semua keragaman ini, algoritma paling sederhana adalah bubble sort, yang dapat diimplementasikan dalam bahasa pemrograman apa pun. Walaupun sederhana, algoritma ini mendasari banyak algoritma yang rumit. Keuntungan lain yang sama pentingnya adalah kesederhanaannya, dan oleh karena itu, dapat diingat dan diterapkan segera, tanpa harus ada literatur tambahan di depan Anda.

Perkenalan

Seluruh Internet modern terdiri dari sejumlah besar jenis struktur data berbeda yang dikumpulkan dalam database. Mereka menyimpan semua jenis informasi, mulai dari data pribadi pengguna hingga inti semantik dari sistem otomatis yang sangat cerdas. Tentu saja, penyortiran data memainkan peran yang sangat penting dalam sejumlah besar informasi terstruktur ini. Penyortiran dapat menjadi langkah wajib sebelum mencari informasi apa pun di database, dan pengetahuan tentang algoritma pengurutan memainkan peran yang sangat penting dalam pemrograman.

Memilah-milah mata mesin dan mata manusia

Bayangkan Anda perlu mengurutkan 5 kolom dengan ketinggian berbeda dalam urutan menaik. Kolom ini dapat berarti segala jenis informasi (harga saham, bandwidth saluran komunikasi, dll.); Anda dapat menyajikan beberapa versi Anda sendiri dari tugas ini agar lebih jelas. Sebagai contoh, kita akan mengurutkan Avengers berdasarkan tinggi badannya: Berbeda dengan program komputer, pengurutan tidak akan menyulitkan Anda karena Anda dapat melihat gambaran keseluruhan dan langsung mengetahui hero mana yang perlu dipindahkan ke mana agar pengurutan berdasarkan ketinggian berhasil diselesaikan. Anda mungkin sudah menebak bahwa untuk mengurutkan struktur data ini dalam urutan menaik, cukup tukar tempat Hulk dan Iron Man:

Selesai!

Dan ini akan menyelesaikan penyortiran dengan sukses. Namun, komputer, tidak seperti Anda, agak bodoh dan tidak melihat keseluruhan struktur data secara keseluruhan. Program kendalinya hanya dapat membandingkan dua nilai pada satu waktu. Untuk mengatasi masalah ini, dia harus memasukkan dua angka ke dalam memorinya dan melakukan operasi perbandingan terhadap angka-angka tersebut, lalu beralih ke pasangan angka lainnya, dan seterusnya hingga semua data telah dianalisis. Oleh karena itu, algoritma pengurutan apa pun dapat disederhanakan dalam tiga langkah:

• Bandingkan dua elemen;
• Tukar atau salin salah satunya;
• Pergi ke elemen berikutnya;

Algoritme yang berbeda dapat melakukan operasi ini dengan cara yang berbeda, namun kita akan melanjutkan untuk mempertimbangkan cara kerja pengurutan gelembung.

Algoritma Pengurutan Gelembung

Penyortiran gelembung dianggap yang paling sederhana, tetapi sebelum menjelaskan algoritme ini, mari kita bayangkan bagaimana Anda mengurutkan Avengers berdasarkan ketinggian jika Anda bisa, seperti mesin, membandingkan hanya dua pahlawan satu sama lain dalam satu periode waktu. Kemungkinan besar, Anda akan melakukan hal berikut (paling optimal):

• Anda pindah ke elemen nol dari array kami (Black Widow);
• Bandingkan elemen nol (Black Widow) dengan yang pertama (Hulk);
• Jika elemen di posisi nol lebih tinggi, Anda menukarnya;
• Sebaliknya, jika elemen pada posisi nol lebih kecil, biarkan elemen tersebut di tempatnya;
• Pindah ke posisi sebelah kanan dan ulangi perbandingannya (bandingkan Hulk dengan Kapten)

Setelah Anda menelusuri seluruh daftar sekaligus dengan algoritma seperti itu, penyortiran tidak akan selesai sepenuhnya. Namun di sisi lain, elemen terbesar dalam daftar akan dipindahkan ke posisi paling kanan. Hal ini akan selalu terjadi, karena begitu Anda menemukan elemen terbesar, Anda akan terus berpindah tempat hingga Anda memindahkannya hingga akhir. Artinya, segera setelah program "menemukan" Hulk dalam array, program akan memindahkannya lebih jauh ke bagian paling akhir daftar: Inilah sebabnya mengapa algoritma ini disebut bubble sort, karena sebagai hasil operasinya, elemen terbesar dalam daftar akan berada di bagian paling atas dari array, dan semua elemen yang lebih kecil akan digeser satu posisi ke kiri: Untuk menyelesaikan pengurutan, Anda perlu kembali ke awal larik dan mengulangi lima langkah yang dijelaskan di atas lagi, sekali lagi berpindah dari kiri ke kanan, membandingkan dan memindahkan elemen sesuai kebutuhan. Tapi kali ini Anda perlu menghentikan algoritma satu elemen sebelum akhir array, karena kita sudah tahu bahwa elemen terbesar (Hulk) benar-benar berada di posisi paling kanan: Jadi programnya harus mempunyai dua loop. Untuk lebih jelasnya, sebelum kita melanjutkan ke review kode programnya, Anda dapat melihat visualisasi cara kerja bubble sort pada link ini: Visualisasi cara kerja bubble sort

Implementasi bubble sort di Java

Untuk mendemonstrasikan cara kerja pengurutan di Java, berikut kode programnya:

• membuat array yang terdiri dari 5 elemen;
• mengunggah kebangkitan para pembalas ke dalamnya;
• menampilkan isi array;
• mengimplementasikan penyortiran gelembung;
• menampilkan kembali array yang diurutkan.

Anda dapat melihat kode di bawah ini, dan bahkan mengunduhnya ke IntelliJ IDE favorit Anda. Ini akan dianalisis di bawah ini:

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
    }
}

Meskipun ada komentar rinci dalam kode, kami memberikan penjelasan tentang beberapa metode yang disajikan dalam program ini. Metode kunci yang menjalankan pekerjaan utama dalam program ini ditulis di kelas ArrayBubble. Kelas berisi konstruktor dan beberapa metode:

• into– metode memasukkan elemen ke dalam array;
• printer– menampilkan isi array baris demi baris;

• toSwap– mengatur ulang elemen jika perlu. Untuk melakukan ini, digunakan variabel sementara dummy, di mana nilai angka pertama ditulis, dan nilai dari angka kedua ditulis sebagai pengganti angka pertama. Isi dari variabel sementara kemudian dituliskan ke angka kedua. Ini adalah teknik standar untuk menukar dua elemen;

  dan akhirnya metode utama:

• bubbleSorter– yang melakukan pekerjaan utama dan mengurutkan data yang disimpan dalam array, kami akan menyajikannya lagi secara terpisah:

  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 memperhatikan dua penghitung: eksternal outdan internal in. Penghitung eksternalout mulai menghitung nilai dari akhir array dan secara bertahap berkurang satu dengan setiap lintasan baru. outDengan setiap pass baru, variabel digeser lebih jauh ke kiri agar tidak mempengaruhi nilai yang sudah diurutkan ke sisi kanan array. Penghitung internalin mulai menghitung nilai dari awal larik dan secara bertahap bertambah satu pada setiap lintasan baru. Peningkatan interjadi hingga mencapai out(elemen terakhir yang dianalisis dalam lintasan saat ini). Loop bagian dalam inmembandingkan dua sel yang berdekatan indan in+1. Jika inbilangan yang disimpan lebih besar dari in+1, maka metode tersebut disebut toSwap, yang menukar tempat kedua bilangan tersebut.

Kesimpulan

Algoritma bubble sort adalah salah satu yang paling lambat. Jika array terdiri dari N elemen, maka perbandingan N-1 akan dilakukan pada lintasan pertama, N-2 pada lintasan kedua, kemudian N-3, dan seterusnya. Artinya, jumlah total lintasan yang akan dilakukan: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Jadi, saat mengurutkan, algoritmanya melakukan sekitar 0,5x(N ^2) perbandingan. Untuk N = 5, jumlah perbandingan akan menjadi sekitar 10, untuk N = 10 jumlah perbandingan akan meningkat menjadi 45. Jadi, seiring bertambahnya jumlah elemen, kompleksitas penyortiran meningkat secara signifikan: Kecepatan algoritma dipengaruhi tidak hanya oleh jumlah pass, namun juga oleh jumlah permutasi yang perlu dilakukan. Untuk data acak, jumlah rata-rata permutasi (N^2) / 4, yaitu sekitar setengah jumlah operan. Namun, dalam kasus terburuk, jumlah permutasi juga bisa N^2 / 2 - ini terjadi jika data awalnya diurutkan dalam urutan terbalik. Meskipun ini adalah algoritma pengurutan yang agak lambat, sangat penting untuk mengetahui dan memahami cara kerjanya, dan, seperti disebutkan sebelumnya, ini adalah dasar untuk algoritma yang lebih kompleks. Benar!