Bubble sort Java

Kung narinig mo na ang mga paraan ng pag-uuri sa programming, malamang na ito ay ang bubble sort algorithm. Ito ay isang sikat. Alam ng bawat programmer ang bubble sort (o hindi bababa sa narinig nito habang nag-aaral) hindi dahil ito ang pinakamahusay na algorithm ng pag-uuri sa mundo, ngunit ang pinakamadali. Ang algorithm na ito ay karaniwang ginagamit para sa mga layunin ng pag-aaral o maaari mo itong makuha bilang isang gawain sa iyong Java Junior Interview. Napakadaling maunawaan ng Java Bubble sort algorithm, gayunpaman, hindi ito mahusay. Anyway, alamin natin ito.

Ano ang pag-uuri

Una sa lahat, kailangan mong maunawaan kung ano ang pag-uuri sa pangkalahatan at kung ano ang maaari naming ayusin sa mga programang Java. Kung maihahambing natin ang dalawa o higit pang elemento o bagay sa alinman sa kanilang mga katangian, nangangahulugan ito na maaari silang pagbukud-bukurin ayon sa katangiang ito. Halimbawa, ang mga numero sa pataas o pababang pagkakasunud-sunod o mga salita ayon sa alpabeto. Samakatuwid, ang mga elemento ay dapat na maihahambing sa bawat isa. Sa pamamagitan ng paraan, ang mga elemento ng ano? Sa Java, maaari nating ihambing ang mga elemento ng Mga Koleksyon. Halimbawa, maaari nating pag-uri-uriin ang Array o ArrayList ng mga integer, Strings at iba pa.

Paano gumagana ang bubble sort

Sabihin nating, kailangan nating pag-uri-uriin ang isang hanay ng mga integer sa pataas na pagkakasunud-sunod, iyon ay, mula sa pinakamaliit hanggang sa pinakamalaking bilang. Una, pupunta tayo sa buong array at ihambing ang bawat 2 kalapit na elemento. Kung sila ay nasa maling pagkakasunud-sunod (ang kaliwang kapitbahay ay mas malaki kaysa sa kanan), pinapalitan namin sila. Sa unang pass sa dulo ito ay lilitaw ang pinakamalaking elemento (kung pag-uri-uriin natin sa pataas na pagkakasunud-sunod). Maaari mong sabihin, ang pinakamalaking elemento ay "lumulutaw". Iyan ang dahilan ng pangalan ng algorithm ng Bubble sort. Ulitin namin ang unang hakbang mula sa una hanggang sa susunod-sa-huling elemento. Mayroon kaming pangalawang pinakamalaking elemento sa susunod-sa-huling lugar. At iba pa. Maaari naming pagbutihin ang isang algorithm nang kaunti sa pamamagitan ng pag-check out kung ang hindi bababa sa isang palitan sa nakaraang hakbang ay ginawa. Kung hindi, hihinto namin ang aming pagtakbo kasama ang array.

Halimbawa ng bubble sort

Pagbukud-bukurin natin ang hanay ng mga integer, ang isa, maaari mong makita sa ibaba sa isang larawan. Hakbang 1: dumadaan tayo sa array. Nagsisimula ang algorithm sa unang dalawang elemento (na may mga indeks na 0 at 1), 8 at 7, at sinusuri kung nasa tamang pagkakasunud-sunod ang mga ito. Obviously, 8 > 7, kaya pinagpalit namin sila. Susunod, tinitingnan natin ang pangalawa at pangatlong elemento (mga indeks 1 at 2), ngayon ito ay 8 at 1. Para sa parehong mga kadahilanan, pinapalitan natin ang mga ito. Sa ikatlong pagkakataon, inihambing namin ang 8 at 2 at, hindi bababa sa 8 at 5. Gumawa kami ng apat na palitan sa kabuuan: (8, 7), (8, 1), (8, 2) at (8, 5). Isang value na 8, ang pinakamalaki sa array na ito, ay lumabas sa dulo ng listahan sa tamang posisyon. Ang resulta ng unang hakbang ng Bubble sort algorithm na gumagana ay ang susunod na array: Hakbang 2. Gawin din ang (7,1), (7,2) at (7,5). Nasa penultimate na posisyon na ngayon ang 7, at hindi na natin kailangang ikumpara ito sa "buntot" ng listahan, nakaayos na ito. Ang resulta ng ikalawang hakbang ng Bubble sort algorithm na gumagana ay ang susunod na array: Gaya ng makikita mo, ang array na ito ay pinagsunod-sunod na. Gayon pa man, ang algorithm ng Bubble Sort ay dapat magpatuloy kahit isang beses. Hakbang 3. Muli kaming dumaan sa array. Walang dapat ipagpalit dito, kaya kung gumagamit kami ng "pinabuting" Bubble Sort algorithm (na may pag-check out kung kahit isang palitan sa nakaraang hakbang ang ginawa) ang hakbang na ito ang huli.

Bubble sort Java code

Bubble sort Java realization

Gumawa tayo ng dalawang paraan para sa Bubble sort. Ang una, ang bubbleSort(int[] myArray) ay isang eroplano. Ito ay tumatakbo sa array sa bawat oras. Ang pangalawa, ang optimizedBubbleSort(int myArray[]) ay na-optimize sa pamamagitan ng paghinto sa algorithm kung ang panloob na loop ay hindi nagdulot ng anumang swap. Ipinapakita sa iyo ng counter kung ilang hakbang ang ginawa mo habang nag-uuri. Narito mayroon kaming Bubble sort Java realization:

import java.util.Arrays;

public class BubbleSortExample {

   //  Plane Bubble sort example

   public static int[] bubbleSort(int[] myArray) {

       int temp = 0;  //  temporary element for swapping
       int counter = 0;  //  element to count quantity of steps

       for (int i = 0; i < myArray.length; i++) {
           counter = i + 1;
           for (int j = 1; j < (myArray.length - i); j++) {

               if (myArray[j - 1] > myArray[j]) {
                   //  swap array’s elements using temporary element
                   temp = myArray[j - 1];
                   myArray[j - 1] = myArray[j];
                   myArray[j] = temp;
               }
           }
       }
       System.out.println("Steps quantity, non optimized = " + counter);
       return myArray;
   }
   //  An optimized version of Java Bubble Sorting

   static int[] optimizedBubbleSort(int myArray[]) {
       int temp;
       boolean swapped;
       int counter = 0;  //  element to count quantity of steps
       for (int i = 0; i < myArray.length - 1; i++) {
           counter = i + 1;
           swapped = false;
           for (int j = 0; j < myArray.length - i - 1; j++) {
               //  counter++;
               if (myArray[j] > myArray[j + 1]) {
                   //  swap arr[j] and arr[j+1]
                   temp = myArray[j];
                   myArray[j] = myArray[j + 1];
                   myArray[j + 1] = temp;
                   swapped = true;

               }
           }  //  counter = i;
           //  If there weren't elements to swap in inner loop, then break
           if (swapped == false) {

               break;

           }
       }
       System.out.println("steps quantity, optimized = " + counter);
       return myArray;
   }


   public static void main(String[] args) {
       int arr[] = {8, 7, 1, 2, 5};
       int arr1[] = {8, 7, 1, 2, 5};

       System.out.println("Array arr Before Bubble Sort");
       //  we use java.util.Arrays toString method to print the array  
 System.out.println(Arrays.toString(arr));

       System.out.println("Array arr After Bubble Sort");
       System.out.println(Arrays.toString(bubbleSort(arr)));

       System.out.println("Array arr1 Before Bubble Sort");
       System.out.println(Arrays.toString(arr1));

       System.out.println("Array arr1 After Optimized Bubble Sort");
       System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
   }
}

Ang resulta ng Bubble sort Java algorithm ay gumagana:

Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]

Gaano kahusay ang pag-uuri ng bubble?

Ang bubble sort ay isa sa mga pinakamadaling algorithm na ipatupad ngunit hindi ito mahusay. Nangangailangan ito ng isang pares ng mga nested na loop. Kahit na sa isang na-optimize na bersyon ng algorithm sa pinakamasamang kaso (bawat elemento ng set ng data ay nasa reverse order sa nais na isa) ang panlabas na loop ay umuulit nang isang beses para sa bawat isa sa mga n elemento ng set ng data. Ang panloob na loop ay umuulit ng n beses sa unang pagkakataon, ( n-1 ) para sa pangalawa, at iba pa. Kaya, upang makuha ang lahat ng n , mga elemento na pinagsunod-sunod, ang mga loop ay kailangang isagawa n*(n-1)/2 beses. Tinatawag nito ang O(n ² )pagiging kumplikado ng oras at nangangahulugan na ang algorithm ay gumagawa ng humigit-kumulang 500 000 paghahambing para sa 1000 elemento ng isang array. Gayunpaman, ang algorithm ng bubble sort ay medyo epektibo sa paggamit ng memory (ang pagiging kumplikado ng memory ay O(n) ) at talagang mahusay para sa halos pinagsunod-sunod na maliliit na dataset.