Балонно сортиране на Java

Ако някога сте чували за методи за сортиране в програмирането, най-вероятно това е бил алгоритъмът за сортиране с мехурчета. Той е известен. Всеки програмист знае балонно сортиране (or поне е чувал за него, докато учи) не защото е най-добрият алгоритъм за сортиране в света, а най-лесният. Този алгоритъм обикновено се използва за учебни цели or може да го получите като задача във вашето Java Junior Interview. Алгоритъмът за сортиране на Java Bubble е много лесен за разбиране, но не е ефективен. Както и да е, нека го разберем.

Какво е сортиране

На първо място, трябва да разберете Howво е сортирането като цяло и Howво можем да сортираме в програмите на Java. Ако можем да сравним два or повече елемента or обекта по някой от техните атрибути, това означава, че те могат да бъдат сортирани по този атрибут. Например числа във възходящ or низходящ ред or думи по азбучен ред. Следователно елементите трябва да са сравними помежду си. Между другото, елементите на Howво? В Java можем да сравним елементите на колекциите. Например можем да сортираме Array or ArrayList от цели числа, низове и т.н.

Как работи балонното сортиране

Да кажем, че трябва да сортираме масив от цели числа във възходящ ред, тоест от най-малкото към най-голямото число. Първо преминаваме по целия масив и сравняваме всеки 2 съседни елемента. Ако са в грешен ред (левият съсед е по-голям от десния), ги разменяме. При първото преминаване в края ще се появи най-големият елемент (ако сортираме във възходящ ред). Може да кажете, че най-големият елемент „изскача“. Това е причината за името на алгоритъма за сортиране с мехурчета. Повтаряме първата стъпка от първия към предпоследния елемент. Имаме втория по големина елемент на предпоследното място. И така нататък. Можем да подобрим малко алгоритъма, като проверим дали е напequals поне един обмен в предишната стъпка. Ако не е, спираме да тичаме по масива.

Пример за балонно сортиране

Нека сортираме масива от цели числа, този, който може да видите по-долу на снимката. Стъпка 1: преминаваме през масива. Алгоритъмът започва с първите два елемента (с индекси 0 и 1), 8 и 7, и проверява дали са в правилния ред. Очевидно 8 > 7, така че ги разменяме. След това разглеждаме втория и третия елемент (индекси 1 и 2), сега това са 8 и 1. По същите причини ги разменяме. За трети път сравняваме 8 и 2 и поне 8 и 5. Направихме общо четири обмена: (8, 7), (8, 1), (8, 2) и (8, 5). Стойност 8, най-голямата в този масив, се появи в края на списъка на правилната позиция. Резултатът от първата стъпка от работата на алгоритъма за сортиране с мехурчета е следващият масив: Стъпка 2. Направете същото с (7,1), (7,2) и (7,5). 7 вече е на предпоследна позиция и не е нужно да го сравняваме с "опашката" на списъка, той вече е сортиран. Резултатът от втората стъпка от работата на алгоритъма за сортиране с мехурчета е следващият масив: Както можете да видите, този масив вече е сортиран. Както и да е, алгоритъмът за Bubble Sort трябва да заработи поне още веднъж. Стъпка 3. Преминаваме още веднъж през масива. Тук няма нищо за размяна, така че ако използваме „подобрен“ алгоритъм за Bubble Sort (с проверка дали е напequals поне един обмен в предишната стъпка), тази стъпка е последната.

Балонно сортиране на Java code

Сортиране на балончета Java реализация

Нека създадем два метода за балонно сортиране. Първият, bubbleSort(int[] myArray) е равнинен. Той преминава през масива всеки път. Вторият, optimizedBubbleSort(int myArray[]) се оптимизира чрез спиране на алгоритъма, ако вътрешният цикъл не е причинил суап. Броячът ви показва колко стъпки сте направor, докато сортирате. Тук имаме Bubble sort Java реализация:

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

Резултатът от работата на 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]

Колко ефективно е балонното сортиране?

Bubble sort е един от най-лесните алгоритми за изпълнение, но не е ефективен. Изисква чифт вложени цикли. Дори в оптимизирана version на алгоритъм в най-лошия случай (всеки елемент от набора от данни е в обратен ред на желания) външният цикъл итерира веднъж за всеки от n елемента от набора от данни . Вътрешният цикъл итерира n пъти за първи път, ( n-1 ) за втори и т.н. Следователно, за да бъдат сортирани всички n елементи, циклите трябва да бъдат изпълнени n*(n-1)/2 пъти. Извиква O(n ² )времева сложност и означава, че алгоритъмът прави около 500 000 сравнения за 1000 елемента от масив. Алгоритъмът за балонно сортиране обаче е доста ефективен при използване на паметта (сложността на паметта е O(n) ) и е наистина добър за почти сортирани малки набори от данни.