Bubble Алгоритъм за сортиране в Java: Програма за сортиране на масиви и пример

Какво е Bubblд Сортиране?

BubblСортирането е прост алгоритъм за сортиране, базиран на сравнение, който сравнява първия елемент от масива със следващия. Ако текущият елемент от масива е числено по-голям от следващия, елементите се разменят. По подобен начин алгоритъмът ще обходи целия елемент от масива.

Алгоритъмът получава името си от начина, по който най-голямата стойност в несортираната област постоянно се издига до крайната си позиция, подобно на балон, издигащ се към повърхността на водата. След първото пълно преминаване, най-големият елемент заема последния индекс. След второто преминаване, вторият по големина елемент се фиксира на място и процесът се повтаря, докато масивът не бъде напълно подреден.

В тази статия ще създадем Java програма за внедряване Bubble Сортиране. Проверете резултата от кода, който ще ви помогне да разберете логиката на програмата, след което прегледайте оптимизираната версия и последващия анализ на сложността.

Как ли BubblРаботи ли алгоритъмът за сортиране?

BubblСортирането работи чрез многократни преминавания през масива. Всяко преминаване преминава от първия индекс до края на текущо несортираната област, сравнявайки съседните стойности и разменяйки ги.ping ги винаги, когато се появят в грешен ред. Тъй като най-голямата оставаща стойност винаги се премества в най-дясната част на несортираната област, областта се свива точно с една позиция след всяко преминаване.

Целият процес може да бъде разделен на четири повтарящи се стъпки:

1. Сравнете: Сравнете елемента с индекс j-1 с елемента с индекс j.
2. Размяна: Ако левият елемент е по-голям от десния елемент, разменете двете стойности, използвайки временна променлива.
3. Advance: Преместете се с една позиция надясно и повторете, докато достигнете края на несортираната област.
4. Повторете: Започнете ново преминаване през регион, който е с един елемент по-къс, и спрете след n-1 преминавания или когато преминаването не извършва размени.

Таблицата по-долу tracе примерният масив {860, 8, 200, 9}, използван в програмата по-нататък на тази страница. Той показва точно коя стойност се установява на крайната си позиция в края на всеки проход.

Обърнете внимание, че третият проход извършва сравнение, но не и размяна. Оптимизираната имплементация открива това условие и спира незабавно, което е най-ценното подобрение, което можете да приложите към този алгоритъм.

BubblПсевдокод на алгоритъма за сортиране

Преди писане Java синтаксис, това помага да се изрази логиката в езиково неутрален псевдокод. Версията по-долу включва флага за ранно излизане, така че обхваща както класическото, така и оптимизираното поведение.

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

Външният цикъл контролира броя на проходите, а вътрешният цикъл контролира сравненията в рамките на един проход. Горната граница на вътрешния цикъл е n – i – 1, защото последните i позиции вече съдържат крайните си стойности.

Java Програма за изпълнение Bubble Сортиране

Следната програма сортира целочислен масив във възходящ ред. Допълнителни оператори за печат са запазени в циклите нарочно, защото четенето на pass-by-pass tracТова е най-бързият начин за начинаещи да разберат как се натрупват суаповете.

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

    }
}

Изход:

---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 обяснение: - сортиране с мехурчета Методът получава масива чрез препратка, така че извикващата страна вижда сортирания резултат без връщана стойност. Променливата ТЕМП съдържа една стойност по време на размяната на три реда, поради което алгоритъмът се нуждае само от O(1) допълнителна памет. Изразът n – i във вътрешния цикъл условието гарантира, че вече сортираните позиции в опашката никога няма да бъдат посетени отново.

Оптимизиран Bubble Сортиране на програмата в Java

Програмата по-горе винаги изпълнява n-1 преминавания, дори когато масивът се сортира рано. Добавянето на един булев флаг коригира тази неефективност. Ако пълното преминаване завърши без нито едно разместване, масивът е гарантирано сортиран и външният цикъл може да спре незабавно.

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

Изход:

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

Входният масив вече беше сортиран, така че оптимизираната версия завърши след едно преминаване вместо след четири. При почти сортирани данни тази промяна превръща квадратичното натоварване в почти линейно, което е основната причина. BubblСортирането все още се появява в реалния код от време на време.

Времева сложност и пространствена сложност на Bubble Сортиране

Сложността описва как времето за изпълнение нараства с нарастването на входния размер. За Bubble Сортирането, броят на сравненията в неоптимизираната версия е фиксиран на n(n-1)/2, което го поставя здраво в квадратичния клас.

Тъй като всеки обмен се случва в оригиналния масив и се използва само една временна променлива, BubblСортирането е алгоритъм на място с O(1) спомагателно пространство. То е и стабилно сортиране, което означава, че два записа, съдържащи един и същ ключ, запазват първоначалния си относителен ред след сортиране.

Предимства и недостатъци на Bubble Сортиране

Разбирането и на двете страни ви помага да решите кога алгоритъмът е приемлив избор и кога трябва да бъде заменен.

Предимства

• Простота: Логиката се побира в приблизително десет реда, което улеснява правилното писане при условия на интервю.
• Работа на място: Не се заделя спомагателен масив, така че използването на памет не нараства с размера на входните данни.
• стабилност: Равните ключове запазват първоначалния си ред, което е важно при сортиране на записи по вторично поле.
• Ранно откриване на излизане: Флагът за размяна идентифицира вече сортиран масив в един проход.

Недостатъци

• Квадратичен растеж: Сортирането на 10 000 елемента изисква близо 50 милиона сравнения в най-лошия случай.
• Прекомерно пише: Алгоритъмът извършва много повече суапове от сортирането чрез селекция, което е скъпоструващо за паметта с бавни операции за запис.
• Слаба мащабируемост: Производствените натоварвания почти винаги предпочитат Quicksort, Merge Sort или вградения метод Arrays.sort.

Bubble Сортиране срещу други видове сортиране Algorithms

Таблицата по-долу прави сравнение Bubble Сортирайте с техниките за сортиране, с които начинаещите се срещат по-нататък, за да можете да видите точно къде печели всяка от тях.

BubblСортирането и сортирането с вмъкване споделят един и същ линеен най-добър случай, но сортирането с вмъкване извършва по-малко размени на частично сортирани данни. Сортирането с селекция винаги извършва точно n-1 размени, което го прави най-tracтивно, когато записите са скъпи, въпреки че това жертва стабилността. За всеки масив, по-голям от няколкостотин елемента, бързото сортиране или сортирането с купчина е правилният избор.

След като се усвоите с моделите за обхождане на масиви, използвани тук, същата структура на цикъла се появява в много класически упражнения, като например Серия на Фибоначи в Java и Java палиндромна програма. Revразглеждане Java масиви и по-широкото Java настойнически ще засили основите, от които зависи този алгоритъм.

Въпроси и Отговори