Java-da köpürjik görnüşini amala aşyrmak

Saýlamak algoritmleriniň köp sanlysy bar, olaryň köpüsi gaty mahsus we dar meseleleri çözmek we maglumatlaryň belli görnüşleri bilen işlemek üçin işlenip düzüldi. Thisöne bu dürlüligiň arasynda iň ýönekeý algoritm, islendik programmirleme dilinde amala aşyrylyp bilinýän köpürjik görnüşidir. Ityönekeýligine garamazdan, köp çylşyrymly algoritmleriň esasyny düzýär. Anotherene-de bir möhüm artykmaçlyk, onuň ýönekeýligi, şonuň üçin öňüňizde goşmaça edebiýat bolmazdan derrew ýatda saklanyp we durmuşa geçirilip bilner.

Giriş

Tutuş häzirki zaman internet maglumatlar bazalarynda toplanan dürli görnüşli maglumat gurluşlaryndan ybaratdyr. Ulanyjylaryň şahsy maglumatlaryndan başlap, ýokary akylly awtomatlaşdyrylan ulgamlaryň semantik ýadrosyna çenli ähli görnüşli maglumatlary saklaýarlar. Elbetde, bu ägirt uly gurluşly maglumatlarda maglumatlary tertiplemek diýseň möhüm rol oýnaýar. Maglumatlar bazasyndaky islendik maglumatlary gözlemezden ozal tertiplemek hökmany ädim bolup biler we algoritmleri tertiplemek bilimleri programmirlemekde möhüm rol oýnaýar.

Maşyn gözleri we adam gözleri boýunça tertiplemek

Geliň, dürli belentlikdäki 5 sütüni ýokarlanýan tertipde tertipleşdirmelidigini göz öňüne getireliň. Bu sütünler islendik maglumaty (paýnamalaryň bahasy, aragatnaşyk kanalynyň geçirijiligi we ş.m.) aňladyp biler; has düşnükli etmek üçin bu meseläniň käbir wersiýalaryny hödürläp bilersiňiz. Mysal üçin, Öwezleri beýiklige görä tertipläris: Kompýuter programmasyndan tapawutlylykda, tertiplemek size kyn bolmaz, sebäbi tutuş suraty görüp bilýärsiňiz we beýikligi boýunça tertipleşdirmegiň üstünlikli tamamlanmagy üçin haýsy gahrymanyň nirä göçürilmelidigini derrew bilip bilersiňiz. Bu maglumat gurluşyny ýokarlanýan tertipde tertiplemek üçin Hulk we Demir adamynyň ýerlerini çalyşmak ýeterlikdir diýip çaklap bilersiňiz.

Boldy!

Bu bolsa sortlamagy üstünlikli tamamlar. Şeýle-de bolsa, kompýuter, sizden tapawutlylykda birneme samsyk we tutuş maglumat gurluşyny görmeýär. Dolandyryş programmasy bir gezekde diňe iki bahany deňeşdirip biler. Bu meseläni çözmek üçin, ýadyna iki san goýmaly we üstünde deňeşdirme amalyny geçirmeli, soň bolsa ähli maglumatlar seljerilýänçä başga bir jübüt sanlara geçmeli we ş.m. Şonuň üçin islendik sortlaşdyryş algoritmi üç ädim görnüşinde gaty ýönekeýleşdirilip bilner:

• Iki elementi deňeşdiriň;
• Olardan birini çalyşmak ýa-da göçürmek;
• Indiki elemente geç;

Dürli algoritmler bu amallary dürli usullar bilen ýerine ýetirip bilerler, ýöne köpürjik görnüşiniň nähili işleýändigini öwrenmäge dowam ederis.

Bubble Sort algoritmi

Köpürjik sortlamak iň ýönekeý hasaplanýar, ýöne bu algoritmi düşündirmezden ozal, bir maşyn ýaly bir wagtyň içinde diňe iki gahrymany biri-biri bilen deňeşdirip bilýän bolsaňyz, Avengers-i beýiklige nädip tertipleşdirjekdigiňizi göz öňüne getireliň. Mümkin, aşakdakylary ýerine ýetirersiňiz (iň amatly):

• Biziň massiwimiziň nol elementine geçýärsiňiz (Gara dul);
• Nol elementini (Gara dul) birinji (Hulk) bilen deňeşdiriň;
• Nol pozisiýadaky element has ýokary bolsa, olary çalyşarsyňyz;
• Otherwiseogsam, nol pozisiýadaky element has kiçi bolsa, olary öz ýerlerinde goýarsyňyz;
• Sag tarapa geçiň we deňeşdirmäni gaýtalaň (Hulk bilen kapitan bilen deňeşdiriň)

Şeýle algoritm bilen bir sanawda tutuş sanawdan geçeniňizden soň, tertipleşdirmek doly tamamlanmaz. Emma beýleki tarapdan, sanawdaky iň uly element iň sag tarapa geçiriler. Bu elmydama bolup geçer, sebäbi iň uly elementi tapanyňyzdan soň, iň soňuna geçýänçäňiz ýerleri hemişe üýtgedersiňiz. .Agny, programma Hulk-y massiwde “tapsa”, ony sanawyň iň soňuna çykarar: Şonuň üçin bu algoritm köpürjik görnüşi diýilýär, sebäbi işleýşiniň netijesinde sanawdaky iň uly element massiwiň iň ýokarsynda bolar we ähli kiçi elementler bir pozisiýany çepe geçirer: Saýlamagy tamamlamak üçin, massiwiň başyna gaýdyp gelmeli we ýokarda beýan edilen bäş ädimi gaýtalamaly, ýene çepden saga geçip, elementleri deňeşdirip we zerur bolanda hereket etmeli. Thisöne bu gezek algoritmi massiw gutarmanka bir elementi duruzmaly, sebäbi iň uly elementiň (Hulk) düýbünden iň dogry ýagdaýdadygyny eýýäm bilýäris: Şonuň üçin programmanyň iki aýlawy bolmaly. Has düşnükli bolmak üçin, programma koduny gözden geçirmezden ozal, köpürjik görnüşiniň nähili işleýändigini görmek üçin bu baglanyşygy ulanyp bilersiňiz: Köpürjik görnüşiniň nähili işleýändigini wizuallaşdyrmak

Java-da köpürjik görnüşini amala aşyrmak

Java-da sortlamagyň nähili işleýändigini görkezmek üçin programma kody:

• 5 elementden ybarat massiw döredýär;
• ar alýanlaryň köpelmegini oňa ýükleýär;
• massiwiň mazmunyny görkezýär;
• köpürjik görnüşini amala aşyrýar;
• tertiplenen massiwi täzeden görkezýär.

Aşakdaky kody görüp, hatda halaýan IntelliJ IDE- ä göçürip alyp bilersiňiz . Aşakda seljeriler:

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

Koddaky jikme-jik düşündirişlere garamazdan, programmada görkezilen käbir usullaryň beýanyny berýäris. Programmanyň esasy işini ýerine ýetirýän esasy usullar ArrayBubble synpynda ýazylýar. Synpda konstruktor we birnäçe usul bar:

• into- elementleri massiwde goýmagyň usuly;
• printer- massiwiň mazmunyny setir boýunça görkezýär;

• toSwap- zerur bolsa elementleri täzeden düzýär. dummyMunuň üçin birinji sanyň bahasy ýazylan we birinji belginiň ýerine ikinji belgiden baha ýazylan wagtlaýyn üýtgeýji ulanylýar . Wagtlaýyn üýtgeýjiniň mazmuny soňra ikinji belgä ýazylýar. Bu iki elementi çalyşmagyň adaty usulydyr;

  we ahyrynda esasy usul:

• bubbleSorter- esasy işi ýerine ýetirýän we massiwde saklanýan maglumatlary tertipleşdirýän bolsa, ony ýene aýratyn görkezeris:

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

Bu ýerde iki hasaplaýja üns bermeli: daşarky outwe içerki in. Daşarky hasaplaýjy,out massiwiň soňundan bahalary sanap başlaýar we her täze geçiş bilen kem-kemden azalýar. outHer täze geçiş bilen üýtgeýji , massiwiň sag tarapynda eýýäm tertiplenen bahalara täsir etmezlik üçin çepe süýşürilýär. Içerki hasaplaýjy,in massiwiň başyndan sanlary sanap başlaýar we her täze geçişde kem-kemden köpelýär. Ösüş inýetýänçä bolup geçýär out(häzirki geçişdäki iň soňky seljerilen element). Içki aýlaw iniki ýanaşyk öýjügi deňeşdirýär inwe in+1. inDükanlarda has köp sanly bolsa , bu iki sanyň ýerini çalyşýan in+1usul diýilýär .toSwap

Netije

Köpürjik sort algoritmi iň haýallardan biridir. Eger massiw N elementlerinden ybarat bolsa, onda birinji geçişde N-1 deňeşdirmeler, ikinjisinde N-2, soň N-3 we ş.m. Passagny, geçişleriň umumy sany ediler: (N-1) + (N-2) + (N-3) +… + 1 = N x (N-1) / 2 Şeýlelik bilen, tertipleşdirilende algoritm takmynan 0,5x (N ^ 2) deňeşdirmeleri ýerine ýetirýär. N = 5 üçin deňeşdirmeleriň sany takmynan 10 bolar, N = 10 üçin deňeşdirmeleriň sany 45-e çenli artar. Şeýlelik bilen, elementleriň sany artdygyça sortlamagyň çylşyrymlylygy ep-esli ýokarlanýar: Algoritmiň tizligine diňe geçişleriň sany däl, eýsem edilmeli permutasiýalaryň sany hem täsir edýär. Tötänleýin maglumatlar üçin permutasiýalaryň ortaça sany (N ^ 2) / 4, bu geçişleriň sanyndan takmynan ýarymdyr. Şeýle-de bolsa, iň erbet ýagdaýda permutasiýalaryň sany hem N ^ 2/2 bolup biler - maglumatlar başda ters tertipde tertiplenen halatynda şeýle bolýar. Munuň gaty haýal sortlaýyş algoritmidigine garamazdan, onuň nähili işleýändigini bilmek we düşünmek gaty möhümdir we ýokarda belläp geçişimiz ýaly has çylşyrymly algoritmleriň esasyny düzýär. Jgd!