Реалізація бульбашкового сортування на Java

Існує досить багато алгоритмів сортування, багато з них дуже специфічні і розроблялися для вирішення вузького кола завдань і роботи з конкретними типами даних. Але серед усього цього різноманіття найпростішим алгоритмом заслужено є бульбашкова сортування, яку можна реалізувати будь-якою мовою програмування. Незважаючи на свою простоту, вона є основою багатьох досить складних алгоритмів. Іншим її не менш важливою перевагою є її простота, а, отже, її можна згадати і реалізувати відразу, не маючи перед очима будь-якої додаткової літератури.

Вступ

Весь сучасний інтернет являє собою безліч різнотипних структур даних, зібраних у бази даних. У них зберігається різноманітна інформація, починаючи від особистих даних користувачів і закінчуючи семантичним ядром високоінтелектуальних автоматизованих систем. Чи варто говорити про те, що сортування даних відіграє дуже важливу роль у цій величезній кількості структурованої інформації. Сортування може стати обов'язковим кроком перед пошуком будь-якої інформації в базі, і знання алгоритмів сортування відіграє важливу роль у програмуванні.

Сортування очима машини та очима людини

Уявімо, що вам потрібно відсортувати за зростанням 5 стовпчиків різної висоти. Під цими стовпчиками може розумітися яка завгодно інформація (ціни на акції, пропускна спроможність каналу зв'язку тощо), можете уявити якийсь свій варіант цього завдання, щоб було наочно. Ну а ми, як приклад, сортуватимемо месників за зростанням: Вам, на відміну від комп'ютерної програми, сортування не складе нікого праці, адже ви здатні бачити картину в цілому і відразу зможете прикинути, якого героя, куди потрібно перемістити, щоб сортування за зростанням було виконано успішно. Ви вже напевно здогадалися, що для сортування за зростанням цієї структури даних достатньо поміняти місцями Халка і Залізну людину:

Done!

І на цьому сортування буде успішно завершено. Однак, обчислювальна машина на відміну від вас дещо тупувата не бачить всю структуру даних цілком. Її програма управління може порівнювати лише два значення за один проміжок часу. Для вирішення цього завдання їй доведеться помістити в свою пам'ять два числа і виконати над ними операцію порівняння, після чого перейти до іншої пари чисел, а так доти, доки не будуть проаналізовані всі дані. Тому будь-який алгоритм сортування дуже спрощено можна уявити у вигляді трьох кроків:

• Порівняти два елементи;
• Поміняти місцями чи скопіювати одне із них;
• Перейти до наступного елемента;

Різні алгоритми можуть по-різному виконувати ці операції, а ми перейдемо до розгляду принципу роботи бульбашкового сортування.

Алгоритм бульбашкового сортування

Пухирцеве сортування вважається найпростішим, але перед тим як описувати цей алгоритм давайте уявімо, як би ви відсортували месників за зростанням, якби могли, як і машина порівнювати між собою лише двох героїв в один проміжок часу. Швидше за все, ви б надійшли (найоптимальнішим) наступним чином:

• Ви рухаєтеся до нульового елементу нашого масиву (Чорна Вдова);
• Порівнюєте нульовий елемент (Чорну Вдову) з першим (Халком);
• Якщо елемент на нульовій позиції виявився вищим, ви міняєте їх місцями;
• Інакше, якщо елемент на нульовій позиції менший, ви залишаєте їх на своїх місцях;
• Здійснюйте перехід на позицію правіше і повторюєте порівняння (порівнюєте Халка з Капітаном)

Після того, як ви пройдете з таким алгоритмом по всьому списку за один прохід, сортування буде здійснено не повністю. Але найбільший елемент у списку буде переміщений в крайню праву позицію. Це буде відбуватися завжди, адже як тільки ви знайдете найбільший елемент, ви весь час мінятимете його місцями поки не перемістите в самий кінець. Тобто як тільки програма «знайде» Халка в масиві, вона рухатиме його далі в кінець списку: Саме тому цей алгоритм називається бульбашковим сортуванням, тому що в результаті його роботи найбільший елемент у списку виявляється в самому верху масиву, а дрібніші елементи будуть зміщені на одну позицію вліво: Щоб завершити сортування, потрібно буде повернутися до початку масиву і повторити описані вище п'ять кроків ще раз, знову переміщаючись зліва направо, порівнюючи та за потребою переміщуючи елементи. Але цього разу вам потрібно зупинити алгоритм за один елемент до кінця масиву, адже ми вже знаємо, що у крайній правій позиції абсолютно точно знаходиться найбільший елемент (Халк): Таким чином, програма повинна мати два цикли. Для більшої наочності, перед тим як ми перейдемо до розгляду програмного коду, за цим посиланням можна ознайомитися з візуалізацією роботи бульбашкового сортування: Візуалізація роботи бульбашкового сортування

Реалізація бульбашкового сортування на мові Java

Для демонстрації роботи сортування на Java, наведемо програмний код, який:

• створює масив на 5 елементів;
• завантажує до нього зростання месників;
• виводить на екран вміст масиву;
• реалізує бульбашкове сортування;
• здійснює повторне виведення на екран відсортованого масиву.

З кодом можна ознайомитись нижче, і навіть завантажити його у свою улюблену IntelliJ IDE. Його розбір проводитиметься нижче:

class ArrayBubble{
    private long[] a;   //Посилання на масив
    private int elems;  //кількість елементів у масиві

    public ArrayBubble(int max){    //конструктор класу
        a = new long[max];          //Створення масиву розміром max
        elems = 0;                  //при створенні масив містить 0 елементів
    }

    public void into(long value){   //метод вставки елемента в масив
        a[elems] = value;           //Вставка value в масив a
        elems++;                    //розмір масиву збільшується
    }

    public void printer(){          //Метод виведення масиву в консоль
        for (int i = 0; i < elems; i++){    //для кожного елемента в масиві
            System.out.print(a[i] + " ");   //Вивести в консоль
            System.out.println("");         //з ​​нового рядка
        }
        System.out.println("----Закінчення виведення масиву----");
    }

    private void toSwap(int first, int second){ //метод змінює місцями пару чисел масиву
        long dummy = a[first];      //У тимчасову змінну поміщаємо перший елемент
        a[first] = a[second];       //на місце першого ставимо другий елемент
        a[second] = dummy;          //замість другого елемента пишемо перший із тимчасової пам'яті
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Зовнішній цикл
            for (int in = 0; in < out; in++){       //Внутрішній цикл
                if(a[in] > a[in + 1])               //Якщо порядок елементів порушено
                    toSwap(in, in + 1);             //викликати метод, що змінює місцями
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Створюємо масив array на 5 елементів

        array.into(163);       //Заповнюємо масив
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //виводимо елементи до сортування
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // знову виводимо відсортований список
    }
}

Не дивлячись на докладні коментарі у коді, наведемо опис деяких методів, які у програмі. Ключові методи, що здійснює основну роботу в програмі, написані в класі ArrayBubble. Клас містить конструктор та кілька методів:

• into– метод вставки елементів у масив;
• printer- Виводить вміст масиву рядково;

• toSwap– переставляє місцями елементи у разі потреби. І тому використовується тимчасова змінна dummy, у якому записується значення першого числа, але в місце першого записується значення з другого числа. Після цього вміст із тимчасової змінної записується у друге число. Це стандартний прийом перестановки подекуди двох елементів;

  і, нарешті, головний метод:

• bubbleSorter– який виконує основну роботу та сортує дані, що зберігаються в масиві, ще раз наведемо його окремо:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Зовнішній цикл
          for (int in = 0; in < out; in++){       //Внутрішній цикл
              if(a[in] > a[in + 1])               //Якщо порядок елементів порушено
                  toSwap(in, in + 1);             //викликати метод, що змінює місцями
          }
      }
  }

Тут слід звернути увагу на два лічильники: зовнішній out, і внутрішній in. Зовнішній лічильникout починає перебір значень з кінця масиву та поступово зменшується з кожним новим проходом на одиницю. Змінна outз кожним новим проходом зміщується все лівіше, щоб не торкатися значень, вже відсортованих у праву частину масиву. Внутрішній лічильникin починає перебір значень початку масиву і поступово збільшується на одиницю кожному новому проході. Збільшення inвідбувається до тих пір, поки він не досягне out(останнього аналізованого елемента в поточному проході). Внутрішній цикл inздійснює порівняння двох сусідніх осередків inі in+1. Якщо inзберігається більше, ніж уin+1, то викликається метод toSwap, який змінює місцями ці два числа.

Висновок

Алгоритм бульбашкового сортування є одним із найповільніших. Якщо масив складається з елементів N, то на першому проході буде виконано N-1 порівнянь, на другому N-2, далі N-3 і т.д. Тобто всього буде виготовлено проходів: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Таким чином, при сортуванні алгоритм виконує близько 0.5х(N ^2) порівнянь. Для N = 5 кількість порівнянь буде приблизно 10, для N = 10 кількість порівнянь виросте до 45. Таким чином, зі збільшенням кількості елементів складність сортування значно збільшується: На швидкість алгоритму впливає як кількість проходів, а й кількість перестановок, які потрібно зробити. Для випадкових даних кількість перестановок у середньому становить (N^2)/4, тобто приблизно половину менше, ніж кількість проходів. Однак, у гіршому випадку кількість перестановок також може становити N^2/2 – це в тому випадку, якщо дані спочатку відсортовані у зворотному порядку. Незважаючи на те, що це досить повільний алгоритм сортування, знати і розуміти, як він працює досить важливо, до того ж, як було сказано раніше, він є основою для складніших алгоритмів. Jgd!