Ако някога сте чували за методи за сортиране в програмирането, най-вероятно това е бил алгоритъмът за сортиране с мехурчета. Той е известен. Всеки програмист знае балонно сортиране (or поне е чувал за него, докато учи) не защото е най-добрият алгоритъм за сортиране в света, а най-лесният. Този алгоритъм обикновено се използва за учебни цели or може да го получите като задача във вашето Java Junior Interview. Алгоритъмът за сортиране на Java Bubble е много лесен за разбиране, но не е ефективен. Както и да е, нека го разберем.
Стъпка 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 поне един обмен в предишната стъпка), тази стъпка е последната.
Какво е сортиране
На първо място, трябва да разберете Howво е сортирането като цяло и Howво можем да сортираме в програмите на Java. Ако можем да сравним два or повече елемента or обекта по някой от техните атрибути, това означава, че те могат да бъдат сортирани по този атрибут. Например числа във възходящ or низходящ ред or думи по азбучен ред. Следователно елементите трябва да са сравними помежду си. Между другото, елементите на Howво? В Java можем да сравним елементите на колекциите. Например можем да сортираме Array or ArrayList от цели числа, низове и т.н.Как работи балонното сортиране
Да кажем, че трябва да сортираме масив от цели числа във възходящ ред, тоест от най-малкото към най-голямото число. Първо преминаваме по целия масив и сравняваме всеки 2 съседни елемента. Ако са в грешен ред (левият съсед е по-голям от десния), ги разменяме. При първото преминаване в края ще се появи най-големият елемент (ако сортираме във възходящ ред). Може да кажете, че най-големият елемент „изскача“. Това е причината за името на алгоритъма за сортиране с мехурчета. Повтаряме първата стъпка от първия към предпоследния елемент. Имаме втория по големина елемент на предпоследното място. И така нататък. Можем да подобрим малко алгоритъма, като проверим дали е нап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]
GO TO FULL VERSION