Bubble Sıralama Algoritması Java: Dizi Sıralama Programı ve Örneği

Nedir? BubblSırala?

BubbleSort, dizinin ilk elemanını bir sonraki elemanla karşılaştıran basit bir karşılaştırma tabanlı sıralama algoritmasıdır. Dizinin mevcut elemanı, bir sonraki elemandan sayısal olarak daha büyükse, elemanlar yer değiştirir. Benzer şekilde, algoritma dizinin tüm elemanlarını tarar.

Algoritma, sıralanmamış bölgedeki en büyük değerin, tıpkı su yüzeyine çıkan bir baloncuk gibi, istikrarlı bir şekilde son konumuna doğru yükselme şeklinden adını almıştır. İlk tam geçişten sonra, en büyük eleman son indeksi işgal eder. İkinci geçişten sonra, ikinci en büyük eleman yerine kilitlenir ve dizi tamamen sıralanana kadar işlem tekrarlanır.

Bu makalede, bir Java uygulanacak program BubbleSort algoritmasını kullanın. Program mantığını anlamanıza yardımcı olacak kod çıktısını inceleyin, ardından optimize edilmiş sürümü ve sonrasında gelen karmaşıklık analizini gözden geçirin.

Nasıl olur BubbleSort Algoritması Çalışıyor mu?

BubbleSort algoritması, dizi üzerinde tekrarlanan geçişler yaparak çalışır. Her geçiş, ilk indeksten şu anda sıralanmamış bölgenin sonuna kadar ilerler, komşu değerleri karşılaştırır ve yer değiştirir.ping Yanlış sırada göründüklerinde onları değiştirirler. En büyük kalan değer her zaman sıralanmamış bölgenin en sağına doğru hareket ettiğinden, bölge her geçişten sonra tam olarak bir pozisyon küçülür.

Tüm süreç dört tekrarlanabilir adıma ayrılabilir:

1. Karşılaştırmak: j-1 indeksindeki elemanı j indeksindeki elemanla karşılaştırın.
2. Swap: Soldaki eleman sağdaki elemandan büyükse, geçici bir değişken kullanarak iki değeri değiştirin.
3. İlerlemek: Bir pozisyon sağa doğru ilerleyin ve sıralanmamış bölgenin sonuna ulaşılana kadar tekrarlayın.
4. Tekrar et: Bir eleman daha az olan bir bölge üzerinde yeni bir geçiş başlatın ve n-1 geçişten sonra veya bir geçişte hiçbir takas işlemi yapılmadığında durun.

Aşağıdaki tablo tracBu, sayfanın ilerleyen kısımlarında programda kullanılan örnek dizi {860, 8, 200, 9}'dur. Her geçişin sonunda hangi değerin nihai konumuna yerleştiğini tam olarak gösterir.

Üçüncü geçişin bir karşılaştırma yaptığını ancak takas işlemi yapmadığını fark edin. Optimize edilmiş bir uygulama bu durumu tespit eder ve hemen durur; bu da bu algoritmaya uygulayabileceğiniz en değerli iyileştirmedir.

Bubble Sıralama Algoritması Sözde Kodu

Yazmadan önce Java Sözdizimi, mantığı dilden bağımsız sözde kodda ifade etmeye yardımcı olur. Aşağıdaki sürüm, erken çıkış bayrağını içerdiğinden hem klasik hem de optimize edilmiş davranışı kapsar.

procedure bubbleSort(array A, integer n)
    for i from 0 to n - 2 do
        swapped := false
        for j from 1 to n - i - 1 do
            // compare the adjacent pair
            if A[j - 1] > A[j] then
                swap A[j - 1] and A[j]
                swapped := true
            end if
        end for
        // no swap in a full pass means the array is sorted
        if swapped = false then
            break
        end if
    end for
end procedure

Dış döngü geçiş sayısını, iç döngü ise tek bir geçiş içindeki karşılaştırmaları kontrol eder. İç döngünün üst sınırı n – i – 1'dir çünkü son i pozisyon zaten nihai değerlerini içermektedir.

Java Uygulama Programı Bubble Sırala

Aşağıdaki program bir tamsayı dizisini artan sırada sıralar. Döngülerin içine bilerek fazladan yazdırma ifadeleri eklenmiştir, çünkü adım adım kodu okumak zor olabilir. tracYeni başlayanlar için takasların nasıl biriktiğini anlamanın en hızlı yolu e harfiyle başlar.

package com.guru99;

public class BubbleSort {

    public static void main(String[] args)
    {
        int arr[] = {860, 8, 200, 9};

        System.out.println("---Array BEFORE Bubble Sort---");

        printArray(arr);

        bubbleSort(arr); //sorting array elements using bubble sort

        System.out.println("---Array AFTER Bubble Sort---");

        printArray(arr);

    }

    static void bubbleSort(int[] array)
    {
        int n = array.length;
        int temp = 0;
        for(int i = 0; i < n; i++) // Looping through the array length
        {   System.out.println("Sort Pass Number " + (i + 1));
            for(int j = 1; j < (n - i); j++)
            {
                System.out.println("Comparing " + array[j - 1] + " and " + array[j]);
                if(array[j - 1] > array[j])
                {
                    //swap elements
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    System.out.println(array[j] + " is greater than " + array[j - 1]);
                    System.out.println("Swapping Elements: New Array After Swap");
                    printArray(array);
                }

            }
        }

    }

    static void printArray(int[] array){

        for(int i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + " ");
        }
        System.out.println();

    }
}

Çıktı:

---Array BEFORE Bubble Sort---
860 8 200 9
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Swapping Elements: New Array After Swap
8 860 200 9
Comparing 860 and 200
860 is greater than 200
Swapping Elements: New Array After Swap
8 200 860 9
Comparing 860 and 9
860 is greater than 9
Swapping Elements: New Array After Swap
8 200 9 860
Sort Pass Number 2
Comparing 8 and 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860
Sort Pass Number 3
Comparing 8 and 9
Sort Pass Number 4
---Array AFTER Bubble Sort---
8 9 200 860

Code açıklama: MKS kabarcık sıralaması Bu metot diziyi referans yoluyla alır, bu nedenle çağıran taraf sıralanmış sonucu herhangi bir dönüş değeri olmadan görür. Değişken temp Üç satırlık takas sırasında tek bir değer tutar, bu nedenle algoritma yalnızca O(1) ek belleğe ihtiyaç duyar. İfade n – i İç döngü koşulu, kuyruktaki önceden sıralanmış pozisyonların asla tekrar ziyaret edilmemesini garanti eder.

Optimize Edilmiş Bubble Programı Sırala Java

Yukarıdaki program, dizi erken sıralansa bile her zaman n-1 geçiş gerçekleştirir. Tek bir mantıksal bayrak eklemek bu verimsizliği giderir. Tam bir geçiş tek bir takas olmadan tamamlanırsa, dizinin sıralanması garanti edilir ve dış döngü hemen durdurulabilir.

package com.guru99;

public class OptimizedBubbleSort {

    public static void main(String[] args) {
        int arr[] = {5, 12, 33, 47, 58};
        bubbleSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }

    static void bubbleSort(int[] array) {
        int n = array.length;
        int passes = 0;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 1; j < n - i; j++) {
                if (array[j - 1] > array[j]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    swapped = true;
                }
            }
            passes++;
            // Early exit: the array is already sorted
            if (!swapped) {
                break;
            }
        }
        System.out.println("Passes executed: " + passes);
    }
}

Çıktı:

Passes executed: 1
[5, 12, 33, 47, 58]

Giriş dizisi zaten sıralıydı, bu nedenle optimize edilmiş sürüm dört geçiş yerine tek geçişte tamamlandı. Neredeyse sıralı verilerde bu değişiklik, karesel bir iş yükünü neredeyse doğrusal bir iş yüküne dönüştürüyor ki bu da ana nedendir. BubbleSort algoritması gerçek kodlarda zaman zaman hala karşımıza çıkıyor.

Zaman Karmaşıklığı ve Alan Karmaşıklığı Bubble Sırala

Karmaşıklık, girdi boyutu arttıkça çalışma süresinin nasıl arttığını açıklar. Bubble Sıralama işleminde, optimize edilmemiş sürümdeki karşılaştırma sayısı n(n-1)/2 olarak sabitlenmiştir; bu da onu kesinlikle ikinci dereceden sınıfa yerleştirir.

Çünkü her değişim orijinal dizi içinde gerçekleşir ve yalnızca bir geçici değişken kullanılır, BubbleSort, O(1) yardımcı alan kullanan yerinde bir algoritmadır. Ayrıca kararlı bir sıralama algoritmasıdır; yani aynı anahtara sahip iki kayıt, sıralamadan sonra orijinal göreceli sıralarını korur.

Avantajları ve Dezavantajları Bubble Sırala

Her iki tarafı da anlamak, algoritmanın ne zaman kabul edilebilir bir seçim olduğunu ve ne zaman değiştirilmesi gerektiğini belirlemenize yardımcı olur.

Avantajlar

• Basitlik: Mantık yaklaşık on satıra sığar, bu da mülakat koşullarında doğru yazmayı kolaylaştırır.
• Yerinde çalışma: Yardımcı bir dizi tahsis edilmediğinden, bellek kullanımı giriş boyutuyla birlikte artmaz.
• Kararlılık: Eşit anahtarlar orijinal sıralarını korur; bu durum, kayıtları ikincil bir alana göre sıralarken önemlidir.
• Erken çıkış tespiti: Değiştirilmiş bayrak, tek geçişte zaten sıralanmış bir diziyi tanımlar.

Dezavantajlar

• İkinci dereceden büyüme: 10,000 öğeyi sıralamak, en kötü senaryoda yaklaşık 50 milyon karşılaştırma gerektirir.
• Aşırı derecede yazıyor: Bu algoritma, yavaş yazma işlemleri nedeniyle bellek açısından maliyetli olan Seçim Sıralaması'na göre çok daha fazla takas işlemi gerçekleştirir.
• Zayıf ölçeklenebilirlik: Üretim ortamındaki iş yüklerinde neredeyse her zaman Quicksort, Merge Sort veya Arrays.sort yöntemi tercih edilir.

BubbleSort ve Diğer Sıralama Yöntemleri Algorithms

Aşağıdaki tablo karşılaştırır BubblAşağıda yeni başlayanların karşılaşacağı sıralama tekniklerini kullanarak e-sıralama yapın, böylece her birinin hangi alanda daha başarılı olduğunu tam olarak görebilirsiniz.

BubblSeçme Sıralaması ve Ekleme Sıralaması aynı doğrusal en iyi duruma sahiptir, ancak Ekleme Sıralaması kısmen sıralanmış verilerde daha az takas gerçekleştirir. Seçme Sıralaması her zaman tam olarak n-1 takas gerçekleştirir, bu da onu en az n-1 takas yapar.tracYazma işlemlerinin maliyetli olduğu durumlarda tercih edilir, ancak kararlılıktan ödün verir. Birkaç yüz elemandan daha büyük herhangi bir dizi için Quicksort veya Heap Sort doğru seçimdir.

Burada kullanılan dizi dolaşım kalıplarına alıştıktan sonra, aynı döngü yapısı birçok klasik alıştırmada da karşınıza çıkacaktır, örneğin... Fibonacci serisi Java ve Java palindrom programı. Revbakış Java diziler ve daha geniş Java öğretici Bu, algoritmanın dayandığı temelleri güçlendirecektir.

SSS