Gelembung urut Jawa

Yen sampeyan wis tau krungu cara ngurutake ing pemrograman, kemungkinan kasebut algoritma pangurutan gelembung. Iku sing misuwur. Saben programer ngerti gelembung sort (utawa paling ora krungu nalika sinau) ora amarga iku algoritma ngurutake paling apik ing donya, nanging sing paling gampang. Algoritma iki biasane digunakake kanggo tujuan sinau utawa sampeyan bisa entuk minangka tugas ing Wawancara SMP Jawa. Algoritma Java Bubble sort gampang banget dimangerteni, nanging ora efisien. Oalah, ayo dipikirake.

Apa sing diurutake

Kaping pisanan, sampeyan kudu ngerti apa ngurutake umume lan apa sing bisa diurutake ing program Java. Yen kita bisa mbandhingake loro utawa luwih unsur utawa obyek kanthi atribut apa wae, tegese bisa diurut miturut atribut iki. Contone, angka ing urutan munggah utawa mudhun utawa tembung miturut abjad. Mula, unsur-unsur kasebut kudu padha karo siji liyane. Miturut cara, unsur apa? Ing Jawa, kita bisa mbandhingake unsur Koleksi. Contone, kita bisa ngurutake Array utawa ArrayList saka integer, Strings lan liya-liyane.

Kepiye cara ngurutake gelembung

Contone, kita kudu ngurutake array integer kanthi urutan munggah, yaiku, saka sing paling cilik nganti sing paling gedhe. Pisanan, kita bakal melu kabeh array lan mbandhingake saben 2 unsur tetanggan. Yen ana ing urutan sing salah (tanggane kiwa luwih gedhe tinimbang sing tengen), kita ganti. Ing pass pisanan ing mburi bakal katon unsur paling gedhe (yen kita Urut ing urutan munggah). Sampeyan bisa ngomong, unsur paling gedhe "muncul". Iku alasan saka jeneng algoritma urutan Gelembung. Kita mbaleni langkah pisanan saka pisanan kanggo unsur sabanjuré-kanggo-pungkasan. Kita entuk unsur paling gedhe nomer loro ing papan sabanjure nganti pungkasan. Lan sateruse. Kita bisa nambah algoritma sethitik karo mriksa metu yen paling siji exchange ing langkah sadurunge wis digawe. Yen ora, kita mandheg mlaku ing sadawane array.

Tuladha ngurutake gelembung

Ayo ngurutake array integer, siji, sampeyan bisa ndeleng ing gambar ing ngisor iki. Langkah 1: kita arep liwat array. Algoritma kasebut diwiwiti kanthi rong unsur pisanan (kanthi indeks 0 lan 1), 8 lan 7, lan mriksa manawa ana ing urutan sing bener. Temenan, 8> 7, mula kita ganti. Sabanjure, kita ndeleng unsur kapindho lan katelu (indeks 1 lan 2), saiki iki 8 lan 1. Kanggo alasan sing padha, kita ngganti. Kanggo kaping telune kita mbandhingake 8 lan 2 lan, paling ora 8 lan 5. Kita nggawe papat ijol-ijolan total: (8, 7), (8, 1), (8, 2) lan (8, 5). Nilai 8, sing paling gedhe ing array iki, muncul ing pungkasan dhaptar menyang posisi sing bener. Asil saka langkah pisanan algoritma Bubble sort yaiku array sabanjure: Langkah 2. Mengkono padha karo (7,1), (7,2) lan (7,5). 7 saiki ing posisi penultimate, lan kita ora perlu kanggo mbandhingaké karo "buntut" dhaftar, iku wis diurutake. Asil saka langkah kapindho algoritma Urut Gelembung digunakake Uploaded sabanjuré: Nalika sampeyan bisa ndeleng, Uploaded iki wis diurutake. Oalah, algoritma Bubble Sort kudu paling sethithik sepisan maneh. Langkah 3. Kita arep liwat array sapisan maneh. Ora ana sing kudu diganti ing kene, dadi yen kita nggunakake algoritma Urut Gelembung "apik" (kanthi mriksa yen paling ora ana siji ijol-ijolan ing langkah sadurunge) langkah iki minangka sing pungkasan.

Gelembung urut kode Jawa

Gelembung urut Jawa realisasi

Ayo nggawe rong cara kanggo ngurutake Gelembung. Sing pertama, bubbleSort(int[] myArray) iku pesawat. Iku mbukak liwat array saben wektu. Sing nomer loro, optimizedBubbleSort(int myArray[]) dioptimalake kanthi mungkasi algoritma kasebut yen loop batin ora nyebabake swap. Counter nuduhake sampeyan carane akeh langkah sing sampeyan tindakake nalika ngurutake. Ing kene kita entuk realisasi Java sort Bubble:

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

Asil saka algoritma Bubble sort Java:

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]

Carane efisien gelembung sort?

Bubble sort minangka salah sawijining algoritma sing paling gampang kanggo dileksanakake nanging ora efisien. Iki mbutuhake sepasang puteran nested. Malah ing versi optimized saka algoritma ing kasus paling awon (saben unsur saka pesawat data ing urutan mbalikke kanggo sing dikarepake) daur ulang njaba sapisan kanggo saben unsur n saka set data. Daur ulang njero diulang kaping n kaping pisanan, ( n-1 ) kanggo kaloro, lan sateruse. Mula, supaya kabeh n , unsur diurutake, puteran kudu dieksekusi n*(n-1)/2 kaping. Iki diarani O(n ² )kerumitan wektu lan tegese algoritma apa bab 500 000 bandingaken kanggo 1000 unsur Uploaded. Nanging, algoritma ngurutake gelembung cukup efektif ing panggunaan memori (kerumitan memori yaiku O (n) ) lan apik banget kanggo kumpulan data cilik sing meh diurutake.