Kabarcık sıralama Java

Programlamada sıralama yöntemlerini daha önce duyduysanız, büyük olasılıkla kabarcık sıralama algoritmasıydı. Ünlü biridir. Her programcı kabarcık sıralamayı bilir (ya da öğrenirken duymuş olabilir), çünkü bu dünyanın en iyi sıralama algoritması değil, en kolayıdır. Bu algoritma genellikle öğrenme amacıyla kullanılır veya Java Junior Röportajınızda bir görev olarak alabilirsiniz. Java Bubble sıralama algoritmasının anlaşılması çok kolaydır, ancak verimli değildir. Her neyse, hadi çözelim.

sıralama nedir

Öncelikle sıralamanın genel olarak ne olduğunu ve Java programlarında neleri sıralayabileceğimizi anlamanız gerekiyor. İki veya daha fazla öğeyi veya nesneyi herhangi bir özniteliğine göre karşılaştırabilirsek, bu, bu özniteliğe göre sıralanabilecekleri anlamına gelir. Örneğin, artan veya azalan sırada sayılar veya alfabetik olarak sözcükler. Bu nedenle, öğeler birbiriyle karşılaştırılabilir olmalıdır. Bu arada, neyin unsurları? Java'da Koleksiyonların öğelerini karşılaştırabiliriz. Örneğin, Array veya ArrayList tamsayıları, Dizeleri vb. sıralayabiliriz.

Kabarcık sıralama nasıl çalışır?

Diyelim ki bir tamsayı dizisini artan düzende, yani en küçükten en büyüğe doğru sıralamamız gerekiyor. İlk olarak, tüm dizi boyunca ilerliyoruz ve her 2 komşu öğeyi karşılaştırıyoruz. Yanlış sıradaysalar (soldaki komşu sağdakinden daha büyük), onları değiştiririz. Sondaki ilk geçişte en büyük öğe görünecektir (artan düzende sıralarsak). En büyük unsur “açılır” diyebilirsiniz. Kabarcık sıralama algoritmasının adının nedeni budur. İlk adımdan sondan sonraki öğeye kadar ilk adımı tekrarlıyoruz. Sondan bir sonraki yerde ikinci en büyük öğeye sahibiz. Ve benzeri. Önceki adımda en az bir değiş tokuş yapılıp yapılmadığını kontrol ederek bir algoritmayı biraz geliştirebiliriz. Değilse, dizi boyunca koşmayı durdururuz.

Kabarcık sıralama örneği

Aşağıda bir resimde görebileceğiniz tamsayı dizisini sıralayalım. Adım 1: Diziyi geçiyoruz. Algoritma ilk iki eleman (0 ve 1 indeksli), 8 ve 7 ile başlar ve doğru sırada olup olmadıklarını kontrol eder. Açıkçası, 8 > 7, bu yüzden onları değiştiriyoruz. Sonra, ikinci ve üçüncü öğelere (1 ve 2 indisleri) bakarız, şimdi bunlar 8 ve 1'dir. Aynı nedenlerle, onları değiştiririz. Üçüncü kez 8 ile 2'yi ve en az 8 ile 5'i karşılaştırıyoruz. Toplamda dört takas yaptık: (8, 7), (8, 1), (8, 2) ve (8, 5). Bu dizinin en büyüğü olan 8 değeri listenin sonunda doğru konuma geldi. Kabarcık sıralama algoritmasının çalışmasının ilk adımının sonucu bir sonraki dizidir: Adım 2. Aynısını (7,1), (7,2) ve (7,5) ile yapmak. 7 şimdi sondan bir önceki konumda ve onu listenin "kuyruğu" ile karşılaştırmamıza gerek yok, zaten sıralandı. Bubble sort algoritmasının ikinci adımının çalışmasının sonucu bir sonraki dizidir: Gördüğünüz gibi bu dizi zaten sıralanmıştır. Her neyse, Kabarcık Sıralama algoritması en az bir kez daha çalışmalıdır. Aşama 3. Diziyi bir kez daha gözden geçiriyoruz. Burada değiştirilecek bir şey yok, dolayısıyla "geliştirilmiş" Kabarcık Sıralama algoritması kullanıyorsak (önceki adımda en az bir değiş tokuşun yapılıp yapılmadığını kontrol ederek) bu adım son adımdır.

Kabarcık sıralama Java kodu

Kabarcık sıralama Java gerçekleştirme

Bubble sort için iki metod oluşturalım. İlki, bubbleSort(int[] myArray) bir düzlemdir. Her seferinde dizi boyunca çalışır. İkincisi, optimizeBubbleSort(int myArray[]), iç döngü herhangi bir takasa neden olmadıysa algoritma durdurularak optimize edilir. Sayaç, sıralama yaparken kaç adım attığınızı gösterir. İşte Kabarcık sıralama Java gerçekleştirmemiz var:

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

Bubble sort Java algoritma çalışmasının sonucu:

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]

Kabarcık sıralama ne kadar verimli?

Kabarcık sıralama, uygulanması en kolay algoritmalardan biridir ancak verimli değildir. Bir çift iç içe döngü gerektirir. Algoritmanın optimize edilmiş bir versiyonunda bile en kötü durumda (veri setinin her elemanı, istenenin tersi sıradadır) dış döngü, veri setinin n elemanının her biri için bir kez yinelenir . İç döngü, ilk kez n kez, ikinci kez ( n-1 ) vb. yinelenir. Bu nedenle, tüm n öğelerini sıralamak için döngülerin n*(n-1)/2 kez yürütülmesi gerekir. O(n ² ) çağırırzaman karmaşıklığıdır ve algoritmanın bir dizinin 1000 öğesi için yaklaşık 500 000 karşılaştırma yapması anlamına gelir. Bununla birlikte, kabarcık sıralama algoritması bellek kullanımında oldukça etkilidir (bellek karmaşıklığı O(n) ) ve neredeyse sıralanmış küçük veri kümeleri için gerçekten iyidir.