Pagpapatupad ng bubble sort sa Java

Mayroong napakaraming bilang ng mga algorithm sa pag-uuri, marami sa mga ito ay napaka-espesipiko at binuo upang malutas ang isang makitid na hanay ng mga problema at gumana sa mga partikular na uri ng data. Ngunit sa lahat ng pagkakaiba-iba na ito, ang pinakasimpleng algorithm ay nararapat na bubble sort, na maaaring ipatupad sa anumang programming language. Sa kabila ng pagiging simple nito, pinagbabatayan nito ang maraming medyo kumplikadong mga algorithm. Ang isa pang pantay na mahalagang bentahe ay ang pagiging simple nito, at, samakatuwid, maaari itong maalala at maipatupad kaagad, nang walang anumang karagdagang literatura sa harap mo.

Panimula

Ang buong modernong Internet ay binubuo ng isang malaking bilang ng iba't ibang uri ng mga istruktura ng data na nakolekta sa mga database. Nag-iimbak sila ng lahat ng uri ng impormasyon, mula sa personal na data ng mga user hanggang sa semantic core ng napakatalinong automated system. Hindi na kailangang sabihin, ang pag-uuri ng data ay gumaganap ng isang napakahalagang papel sa malaking halaga ng nakabalangkas na impormasyon. Ang pag-uuri ay maaaring maging isang mandatoryong hakbang bago maghanap ng anumang impormasyon sa database, at ang kaalaman sa pag-uuri ng mga algorithm ay gumaganap ng isang napakahalagang papel sa programming.

Pag-uuri sa pamamagitan ng mga mata ng makina at mga mata ng tao

Isipin natin na kailangan mong pagbukud-bukurin ang 5 column ng iba't ibang taas sa pataas na pagkakasunud-sunod. Ang mga column na ito ay maaaring mangahulugan ng anumang uri ng impormasyon (mga presyo ng stock, bandwidth ng channel ng komunikasyon, atbp.); maaari mong ipakita ang ilan sa iyong sariling mga bersyon ng gawaing ito upang gawin itong mas malinaw. Well, bilang isang halimbawa, pag-uuri-uriin namin ang Avengers ayon sa taas: Hindi tulad ng isang computer program, hindi magiging mahirap para sa iyo ang pag-uuri, dahil nakikita mo ang buong larawan at agad mong malalaman kung aling bayani ang kailangang ilipat kung saan upang matagumpay na makumpleto ang pag-uuri ayon sa taas. Marahil ay nahulaan mo na na upang pag-uri-uriin ang istraktura ng data na ito sa pataas na pagkakasunud-sunod, palitan lamang ang mga lugar ng Hulk at Iron Man:

Tapos na!

At ito ay makukumpleto ng matagumpay na pag-uuri. Gayunpaman, ang computer, hindi katulad mo, ay medyo hangal at hindi nakikita ang buong istraktura ng data sa kabuuan. Ang control program nito ay maaari lamang maghambing ng dalawang halaga sa isang pagkakataon. Upang malutas ang problemang ito, kakailanganin niyang maglagay ng dalawang numero sa kanyang memorya at magsagawa ng paghahambing na operasyon sa mga ito, at pagkatapos ay lumipat sa isa pang pares ng mga numero, at iba pa hanggang sa masuri ang lahat ng data. Samakatuwid, ang anumang algorithm ng pag-uuri ay maaaring maging napakasimple sa anyo ng tatlong hakbang:

• Paghambingin ang dalawang elemento;
• Magpalit o kopyahin ang isa sa mga ito;
• Pumunta sa susunod na elemento;

Maaaring isagawa ng iba't ibang algorithm ang mga operasyong ito sa iba't ibang paraan, ngunit magpapatuloy kami upang isaalang-alang kung paano gumagana ang pag-uuri ng bubble.

Bubble Sort Algorithm

Ang pag-uuri ng bubble ay itinuturing na pinakasimple, ngunit bago ilarawan ang algorithm na ito, isipin natin kung paano mo pag-uuri-uriin ang Avengers ayon sa taas kung maaari mong, tulad ng isang makina, ihambing lamang ang dalawang bayani sa isa't isa sa isang yugto ng panahon. Malamang, gagawin mo ang sumusunod (pinakamahusay):

• Lumipat ka sa element zero ng aming array (Black Widow);
• Ihambing ang zero na elemento (Black Widow) sa una (Hulk);
• Kung mas mataas ang elemento sa posisyong zero, palitan mo sila;
• Kung hindi, kung mas maliit ang elemento sa posisyong zero, iiwan mo sila sa kanilang mga lugar;
• Lumipat sa isang posisyon sa kanan at ulitin ang paghahambing (ihambing ang Hulk sa Kapitan)

Pagkatapos mong suriin ang buong listahan sa isang pass na may ganoong algorithm, ang pag-uuri ay hindi makukumpleto nang buo. Ngunit sa kabilang banda, ang pinakamalaking elemento sa listahan ay ililipat sa pinakakanang posisyon. Ito ay palaging mangyayari, dahil sa sandaling mahanap mo ang pinakamalaking elemento, patuloy kang magbabago ng mga lugar hanggang sa ilipat mo ito sa pinakadulo. Iyon ay, sa sandaling "mahanap" ng programa ang Hulk sa array, ililipat siya nito sa pinakadulo ng listahan: Ito ang dahilan kung bakit ang algorithm na ito ay tinatawag na bubble sort, dahil bilang resulta ng operasyon nito, ang pinakamalaking elemento sa listahan ay nasa pinakatuktok ng array, at lahat ng mas maliliit na elemento ay ililipat ng isang posisyon sa kaliwa: Upang makumpleto ang pag-uuri, kakailanganin mong bumalik sa simula ng array at ulitin muli ang limang hakbang na inilarawan sa itaas, muli na gumagalaw mula kaliwa pakanan, paghahambing at paglipat ng mga elemento kung kinakailangan. Ngunit sa pagkakataong ito kailangan mong ihinto ang algorithm ng isang elemento bago matapos ang array, dahil alam na natin na ang pinakamalaking elemento (Hulk) ay ganap na nasa pinakakanang posisyon: Kaya ang programa ay dapat magkaroon ng dalawang mga loop. Para sa higit na kalinawan, bago tayo magpatuloy sa pagsusuri sa code ng programa, makakakita ka ng visualization kung paano gumagana ang bubble sort sa link na ito: Visualization kung paano gumagana ang bubble sort.

Pagpapatupad ng bubble sort sa Java

Upang ipakita kung paano gumagana ang pag-uuri sa Java, narito ang code ng programa:

• lumilikha ng hanay ng 5 elemento;
• ina-upload ang pagtaas ng mga naghihiganti dito;
• ipinapakita ang mga nilalaman ng array;
• nagpapatupad ng bubble sort;
• muling ipinapakita ang pinagsunod-sunod na hanay.

Maaari mong tingnan ang code sa ibaba, at kahit na i-download ito sa iyong paboritong IntelliJ IDE. Ito ay susuriin sa ibaba:

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

Sa kabila ng mga detalyadong komento sa code, nagbibigay kami ng paglalarawan ng ilan sa mga pamamaraan na ipinakita sa programa. Ang mga pangunahing pamamaraan na nagsasagawa ng pangunahing gawain sa programa ay nakasulat sa klase ng ArrayBubble. Ang klase ay naglalaman ng isang constructor at ilang mga pamamaraan:

• into– paraan ng pagpasok ng mga elemento sa isang array;
• printer– ipinapakita ang mga nilalaman ng array linya sa pamamagitan ng linya;

• toSwap– muling ayusin ang mga elemento kung kinakailangan. Upang gawin ito, ginagamit ang isang pansamantalang variable dummy, kung saan isinulat ang halaga ng unang numero, at sa lugar ng unang numero ay isinulat ang halaga mula sa pangalawang numero. Ang mga nilalaman mula sa pansamantalang variable ay isinusulat sa pangalawang numero. Ito ay isang karaniwang pamamaraan para sa pagpapalit ng dalawang elemento;

  at sa wakas ang pangunahing pamamaraan:

• bubbleSorter– na gumagawa ng pangunahing gawain at nag-uuri ng data na nakaimbak sa array, ipapakita namin ito nang hiwalay muli:

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

Dito dapat mong bigyang pansin ang dalawang counter: panlabas outat panloob in. Ang panlabas na counterout ay nagsisimula sa pag-enumerate ng mga halaga mula sa dulo ng array at unti-unting bumababa ng isa sa bawat bagong pass. outSa bawat bagong pass, ang variable ay inililipat pa sa kaliwa upang hindi maapektuhan ang mga value na nakaayos na sa kanang bahagi ng array. Ang panloob na counterin ay nagsisimula sa pagbilang ng mga halaga mula sa simula ng array at unti-unting tumataas ng isa sa bawat bagong pass. Ang pagtaas inay nangyayari hanggang sa umabot ito out(ang huling nasuri na elemento sa kasalukuyang pass). Inihahambing ng panloob na loop inang dalawang katabing mga cell inat in+1. Kung inang isang mas malaking numero ay nakaimbak sa kaysa sa in+1, kung gayon ang pamamaraan ay tinatawag na toSwap, na nagpapalit ng mga lugar ng dalawang numerong ito.

Konklusyon

Ang bubble sort algorithm ay isa sa pinakamabagal. Kung ang array ay binubuo ng N elemento, ang N-1 na paghahambing ay isasagawa sa unang pass, N-2 sa pangalawa, pagkatapos ay N-3, atbp. Ibig sabihin, ang kabuuang bilang ng mga pass ay gagawin: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Kaya, kapag nag-uuri, ang algorithm gumaganap ng mga 0.5x(N ^2) na paghahambing. Para sa N = 5, ang bilang ng mga paghahambing ay magiging humigit-kumulang 10, para sa N = 10 ang bilang ng mga paghahambing ay tataas sa 45. Kaya, habang ang bilang ng mga elemento ay tumataas, ang pagiging kumplikado ng pag-uuri ay tumataas nang malaki: Ang bilis ng algorithm ay apektado hindi lamang ng bilang ng mga pass, kundi pati na rin ng bilang ng mga permutasyon na kailangang gawin. Para sa random na data, ang bilang ng mga permutasyon ay nasa average (N^2) / 4, na halos kalahati ng bilang ng mga pass. Gayunpaman, sa pinakamasamang kaso, ang bilang ng mga permutasyon ay maaari ding maging N^2 / 2 - ito ang kaso kung ang data ay unang inayos sa reverse order. Sa kabila ng katotohanan na ito ay isang medyo mabagal na algorithm ng pag-uuri, ito ay lubos na mahalaga na malaman at maunawaan kung paano ito gumagana, at, tulad ng nabanggit kanina, ito ang batayan para sa mas kumplikadong mga algorithm. Jgd!