Implementasi bubble sort in Java

Ana akeh algoritma ngurutake, akeh sing spesifik banget lan dikembangake kanggo ngatasi masalah sing sempit lan nggarap jinis data tartamtu. Nanging ing antarane kabeh macem-macem iki, algoritma sing paling gampang yaiku jinis gelembung, sing bisa ditindakake ing basa pamrograman apa wae. Senadyan kesederhanaan kasebut, ana akeh algoritma sing rada rumit. Kauntungan liyane sing padha penting yaiku kesederhanaan, lan mula bisa dieling-eling lan ditindakake kanthi cepet, tanpa ana literatur tambahan ing ngarep sampeyan.

Pambuka

Kabeh Internet modern dumadi saka macem-macem jinis struktur data sing diklumpukake ing basis data. Dheweke nyimpen kabeh jinis informasi, saka data pribadhi pangguna nganti inti semantik sistem otomatis sing cerdas. Ora perlu dikandhakake, ngurutake data nduweni peran sing penting banget ing jumlah informasi terstruktur iki. Ngurutake bisa dadi langkah wajib sadurunge nggoleki informasi apa wae ing basis data, lan kawruh ngurutake algoritma nduweni peran sing penting banget ing pemrograman.

Ngurutake liwat mata mesin lan mata manungsa

Coba bayangake sampeyan kudu ngurutake 5 kolom kanthi dhuwur sing beda-beda ing urutan munggah. Kolom kasebut bisa ateges informasi apa wae (rega saham, bandwidth saluran komunikasi, lsp.); sampeyan bisa nampilake sawetara versi tugas iki dhewe supaya luwih jelas. Dadi, minangka conto, kita bakal ngurutake Avengers miturut dhuwur: Ora kaya program komputer, ngurutake ora bakal angel kanggo sampeyan, amarga sampeyan bisa ndeleng kabeh gambar lan langsung bisa nemtokake pahlawan sing kudu dipindhah menyang ngendi supaya ngurutake kanthi dhuwur bisa rampung kanthi sukses. Sampeyan mbokmenawa wis ngira yen kanggo ngurutake struktur data iki kanthi urutan munggah, mung ganti panggonan Hulk lan Iron Man:

Rampung!

Lan iki bakal ngrampungake ngurutake kanthi sukses. Nanging, komputer, ora kaya sampeyan, rada bodho lan ora ndeleng kabeh struktur data kanthi sakabehe. Program kontrol kasebut mung bisa mbandhingake rong nilai sekaligus. Kanggo ngatasi masalah iki, dheweke kudu nyelehake rong nomer ing memori lan nindakake operasi perbandingan, banjur pindhah menyang pasangan nomer liyane, lan sateruse nganti kabeh data wis dianalisis. Mulane, algoritma ngurutake apa wae bisa disederhanakake kanthi telung langkah:

• Mbandhingake rong unsur;
• Ganti utawa nyalin salah sijine;
• Pindhah menyang unsur sabanjure;

Algoritma sing beda-beda bisa nindakake operasi kasebut kanthi cara sing beda-beda, nanging kita bakal terus mikir babagan cara kerja gelembung.

Algoritma Urut Gelembung

Ngurutake gelembung dianggep paling gampang, nanging sadurunge njlentrehake algoritma iki, ayo bayangake carane sampeyan ngurutake Avengers kanthi dhuwur yen sampeyan bisa, kaya mesin, mbandhingake mung rong pahlawan ing siji wektu. Paling kamungkinan, sampeyan bakal nindakake ing ngisor iki (paling optimal):

• Sampeyan pindhah menyang unsur nul array kita (Black Widow);
• Mbandhingaké unsur nul (Black Widow) karo pisanan (Hulk);
• Yen unsur ing posisi nul luwih dhuwur, sampeyan ngganti;
• Yen ora, yen unsur ing posisi nul luwih cilik, sampeyan ninggalake ing panggonan;
• Pindhah menyang posisi ing sisih tengen lan baleni mbandhingake (bandhingake Hulk karo Kapten)

Sawise sampeyan mbukak kabeh dhaptar ing siji pass karo algoritma kuwi, ngurutake ora bakal rampung rampung. Nanging ing sisih liya, unsur paling gedhe ing dhaptar bakal dipindhah menyang posisi paling tengen. Iki mesthi kedadeyan, amarga yen sampeyan nemokake unsur paling gedhe, sampeyan bakal terus-terusan ngganti papan nganti sampeyan pindhah menyang pungkasan. Sing, sanalika program "nemokake" Hulk ing larik, iku bakal mindhah luwih kanggo mburi dhaftar: Mulane algoritma iki diarani urutan gelembung, amarga minangka asil operasi, unsur paling gedhe ing dhaptar bakal ana ing sisih ndhuwur array, lan kabeh unsur sing luwih cilik bakal dialihake siji posisi ing sisih kiwa: Kanggo ngrampungake urutan kasebut, sampeyan kudu bali menyang wiwitan array lan baleni maneh limang langkah sing diterangake ing ndhuwur, maneh pindhah saka kiwa menyang tengen, mbandhingake lan mindhah unsur yen perlu. Nanging wektu iki sampeyan kudu mungkasi algoritma siji unsur sadurunge mburi Uploaded, amarga kita wis ngerti sing unsur paling gedhe (Hulk) pancen ana ing posisi paling tengen: Dadi program kudu duwe rong puteran. Kanggo luwih gamblang, sadurunge nerusake kanggo nliti kode program, sampeyan bisa ndeleng visualisasi carane ngurutake gelembung ing link iki: Visualisasi carane ngurutake gelembung bisa digunakake.

Implementasi bubble sort ing basa Jawa

Kanggo nduduhake cara ngurutake ing Jawa, iki kode program:

• nggawe array saka 5 unsur;
• unggahan munggah saka avengers menyang;
• nampilake isi array;
• ngleksanakake urutan gelembung;
• nampilake maneh array sing diurutake.

Sampeyan bisa ndeleng kode ing ngisor iki, lan malah download menyang IntelliJ IDE favorit. Bakal dianalisis ing ngisor iki:

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

Senadyan komentar rinci ing kode, kita nyedhiyani gambaran saka sawetara cara presented ing program. Cara utama sing nindakake pakaryan utama ing program kasebut ditulis ing kelas ArrayBubble. Kelas kasebut ngemot konstruktor lan sawetara metode:

• into- cara nglebokake unsur menyang larik;
• printer- nampilake isi baris array kanthi baris;

• toSwap- ngatur maneh unsur yen perlu. Kanggo nindakake iki, variabel sauntara digunakake dummy, ing ngendi nilai nomer pisanan ditulis, lan ing panggonan nomer pisanan nilai saka nomer kaloro ditulis. Isi saka variabel sauntara banjur ditulis menyang nomer kapindho. Iki minangka teknik standar kanggo ngganti rong unsur;

  lan pungkasane cara utama:

• bubbleSorter- sing nindakake pakaryan utama lan ngurutake data sing disimpen ing array, kita bakal nampilake kanthi kapisah maneh:

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

Kene sampeyan kudu mbayar manungsa waé kanggo loro counters: external outlan internal in. Counter eksternalout miwiti enumerasi nilai saka mburi array lan mboko sithik mudhun siji saben pass anyar. outKanthi saben pass anyar, variabel dipindhah menyang sisih kiwa supaya ora mengaruhi nilai sing wis diurutake ing sisih tengen array. Counter internalin miwiti enumerasi nilai saka wiwitan array lan mboko sithik nambah siji ing saben pass anyar. Tambah inana nganti tekan out(unsur analisa pungkasan ing pass saiki). Daur ulang njero inmbandhingake rong sel jejer inlan in+1. Yen innomer luwih disimpen ing saka in+1, banjur cara disebut toSwap, kang swaps panggonan nomer loro iki.

Kesimpulan

Algoritma ngurutake gelembung minangka salah sawijining sing paling alon. Yen array kasusun saka unsur N, banjur N-1 bandingaken bakal dileksanakake ing pass pisanan, N-2 ing kaloro, banjur N-3, etc. Tegese, jumlah total pass bakal ditindakake: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Mangkono, nalika ngurutake, algoritma nindakake babagan 0,5x (N ^ 2) mbandhingake. Kanggo N = 5, jumlah mbandhingake bakal kira-kira 10, kanggo N = 10 jumlah mbandhingake bakal nambah dadi 45. Dadi, nalika jumlah unsur mundhak, kerumitan ngurutake mundhak sacara signifikan: Kacepetan algoritma kasebut ora mung kena pengaruh jumlah pass, nanging uga jumlah permutasi sing kudu ditindakake. Kanggo data acak, jumlah permutasi rata-rata (N^2) / 4, yaiku kira-kira setengah saka jumlah pass. Nanging, ing kasus sing paling awon, jumlah permutasi bisa uga N ^ 2 / 2 - iki kedadeyan yen data wiwitane diurutake kanthi urutan mbalikke. Senadyan kasunyatan sing iki algoritma ngurutake rada alon, iku cukup penting kanggo ngerti lan ngerti cara kerjane, lan, minangka kasebut sadurungé, iku basis kanggo algoritma liyane Komplek. Jgd!