Notatka: Sortowanie bąbelkowe
Zacząłem sobie przypominać czy też uczyć się algorytmów, ostatnio przerobiłem drzewo binarne jako strukturę danych, dzisiaj zabiorę się za Sortowanie Bąbelkowe.
Na czym polega ten algorytm?
Jak sama nazwa wskazuje jest to algorytm sortujący dane, nie jest on najszybszy ale o tym za chwilę. Algorytm ten jest stosunkowo prosty w implementacji. Swoją nazwę wziął od tego, że największa liczba w sortowanej kolekcji jest podobna do pęcherzyka powietrza (bąbelka) wypływającego pod wpływam ciśnienia z wody. Tutaj tak samo tutaj “wypychamy” największą liczbę na ostatnie miejsce (też zależy w którą stronę sortujemy). Efekt ten uzyskuję się poprzez zamianę dwóch sąsiadujących elementów kolekcji, w taki sposób, że gdy liczba na pozycji N jest mniejsza niż następna czyli N+1 to trzeba je zamienić miejscami.
Przykład:
Dłuższy przykład można zobaczyć tutaj: link. Pan programista (jak mniemam) świetnie pokazuje przykład sortowania bąbelkowego krok po kroku, polecam. Ja pokaże to tylko na 4 liczbach:
[4, 1, 3, 2]
Aby posortować taką tablicę należy wykonać następujące czynności:
- porównać 4 i 1, 4 jest większe więc zamieniamy z 1 i jest: [1, 4, 3, 2]
- porównać 4 i 3, 4 jest większe więc zamieniamy z 3 i jest: [1, 3, 4, 2]
- porównać 4 i 2, 4 jest większe wiec zamieniamy z 2 i jest: [1, 3, 2, 4]
W ten sposób “przepchnęliśmy” największą liczbę czyli 4 na koniec kolekcji. Oczywiście to nie koniec bo taką operację trzeba powtórzyć tak aby całość była przesortowana. Złożoność obliczeniowa w najgorszym przypadku to O(n2) więc może to trochę potrwać. Zatem dalej porównując:
- porównać 1 i 3, 1 jest mniejsze więc zostaje na swojej pozycji
- porównać 3, 2, 3 jest większe więc zamieniamy z 2 i jest: [1, 2, 3, 4]
- porównać 3 i 4, 3 jest mniejsze więc zostaje na swojej pozycji
Mogło by się wydawać, że to już koniec ale w niezoptymalizowanej wersji algorytmu wykona się to wszystko jeszcze raz pomimo, że kolekcja jest już posortowana.
Złożoność obliczeniowa i optymalizacja
W najgorszym przypadku jest to właśnie O(n2), jeśli użyjemy optymalizacji można w najlepszym przypadku zejść do O(n) a w typie optymalizacji użytym na filmie O(n) i złożoności pamięci O(1). Tak jak pokazał to Pan na filmie, można to zoptymalizować na 2 sposoby. Ja pisząc swój algorytm na początku z głowy, szukając czy dałoby się to napisać funkcyjnie, natknąłem się na inne możliwości zapisu algorytmu a także kolejną formę optymalizacji.
- Optymalizacja 1 – brak sprawdzania całości jeszcze raz po przesortowaniu, trzeba dołożyć dodatkową flagę i jeśli nie było “zamian” w poprzednim przejściu to zakończyć pętlę sprawdzania bo mamy już tablicę przesortowaną na 100%
- Optymalizacja 2 – brak sprawdzania liczb które są najbardziej od prawej, w skrócie jeśli mamy 2,1, 3, 6, 7, 8 to po co sprawdzać za każdym następnym przejściem 6, 7, 8? Przecież one już się nie zmienią. Czyli jeśli nie było zamiany z ostatnią pozycją to zmniejszamy długość sprawdzania o 1 i tak za każdym razem.
- Optymalizacja 3 – znaleziona tu, jest to jakby połączenie dwóch poprzednich optymalizacji, algorytm zatrzymuje się jeśli w poprzednim przebiegu nie było żadnej zmiany oraz nie uwzględnia ostatnich pozycji
Kod:
Aby pokazać różnice czasowe i ilości porównań stworzyłem sobie klasę implementującą 3 interfejsy, Sort, OptimizedSort, SuperOptimizedSort (tak wiem nazwy mogłyby być lepsze :)). Są 3 i są generyczne, ponieważ mogą mi się jeszcze przydać przy następnych algorytmach i dla innych typów, poza tym zachowana zostaje zasada Segregacji Interfejsów (I w mnemoniku SOLID). Następnie zaimplementowałem w klasie BubbleSort wszystkie 3 metody (po jednej z każdego interfejsu). Następnie wrzuciłem to w wątki bo przy większych liczbach może to być czasowo problematyczne. Dodałem też drukowanie ilości porównań wewnątrz algorytmu.
Interfejsy:
public interface SortAlgorithm> {
T[] sort(T[] arrayToSort);
}
public interface OptimizedSort> {
T[] optimizedSort(T[] arrayToSort);
}
public interface SuperOptimizedSort {
T[] mostOptimizedSort(T[] arrayToSort);
} Klasa BubbleSort:
package sorting;
import static java.lang.String.format;
public class BubbleSort> implements SortAlgorithm, OptimizedSort, SuperOptimizedSort {
//iteration way, non optimized
@Override
public T[] sort(T[] arrayToSort) {
int count = 0;
for (int i = 0; i < arrayToSort.length - 1; i++) {
for (int j = 0; j < arrayToSort.length - 1; j++) {
count++;
if (arrayToSort[j].compareTo(arrayToSort[j + 1]) > 0) {
swapElements(arrayToSort, j, j + 1);
}
}
}
printNumberOfComparisions(count, "(non optimized)");
return arrayToSort;
}
//optimized sort with additional flag
@Override
public T[] optimizedSort(T[] arrayToSort) {
int count = 0;
boolean swapped = true;
for (int i = 1; i < arrayToSort.length && swapped; i++) {
swapped = false;
for (int j = 0; j < arrayToSort.length - i; j++) {
count++;
if (arrayToSort[j].compareTo(arrayToSort[j + 1]) > 0) {
swapElements(arrayToSort, j, j + 1);
swapped = true;
}
}
}
printNumberOfComparisions(count, "(optimized)");
return arrayToSort;
}
/* optimized way 1 + 2 from here: http://www.algorytm.org/algorytmy-sortowania/sortowanie-babelkowe-bubblesort/bubble-3-j.html */
@Override
public T[] mostOptimizedSort(T[] arrayToSort) {
int count = 0;
int n = arrayToSort.length - 1;
while (n > 0) {
int last = 0;
for (int j = 0; j < n; j++) {
count++;
if (arrayToSort[j].compareTo(arrayToSort[j + 1]) > 0) {
swapElements(arrayToSort, j, j + 1);
last = j;
}
}
n = last;
}
printNumberOfComparisions(count, "(most optimized)");
return arrayToSort;
}
private void swapElements(T[] arrayToSort, int i, int j) {
T temp = arrayToSort[i];
arrayToSort[i] = arrayToSort[j];
arrayToSort[j] = temp;
}
private void printNumberOfComparisions(int count, String typeOfOptimization) {
System.out.printf("Number of comparisions %s: %d%n", typeOfOptimization, count);
}
} Klasa Main gdzie tworze sobie wątki:
import java.util.Arrays;
import java.util.Random;
public class Main {
public static void main(String[] args) throws InterruptedException {
Random random = new Random();
Integer[] array = new Integer[1000];
final int length = array.length;
array = Arrays.stream(array).map(x -> random.nextInt(length)).toArray(Integer[]::new);
final Integer[] copyOfArray = Arrays.copyOf(array, array.length);
Thread t = getThreadWithTimeCounter(() -> printAfterSort(copyOfArray), "non-sorted");
t.start();
Thread t1 = getThreadWithTimeCounter(() -> printAfterOptimizedSort(copyOfArray), "optimized");
t1.start();
Thread t2 = getThreadWithTimeCounter(() -> printAfterMostOptimizedSort(copyOfArray), "most-optimized");
t2.start();
}
private static Thread getThreadWithTimeCounter(Runnable runnable, String name) {
Thread t = new Thread(() -> {
long startTime = System.currentTimeMillis();
runnable.run();
long endTime = System.currentTimeMillis();
System.out.printf("Time in millis for runnable %s %d%n", name, endTime - startTime);
});
return t;
}
private static void printAfterSort(Integer[] array) {
Integer[] copy = Arrays.copyOf(array, array.length);
BubbleSort bubbleSort = new BubbleSort<>();
bubbleSort.sort(copy);
// System.out.println(Arrays.toString(bubbleSort.sort(copy)));
}
private static void printAfterOptimizedSort(Integer[] array) {
Integer[] copy = Arrays.copyOf(array, array.length);
OptimizedSort optimizedSort = new BubbleSort<>();
optimizedSort.optimizedSort(copy);
// System.out.println(Arrays.toString(optimizedSort.optimizedSort(copy)));
}
private static void printAfterMostOptimizedSort(Integer[] array) {
Integer[] copy = Arrays.copyOf(array, array.length);
SuperOptimizedSort bubbleSort = new BubbleSort<>();
bubbleSort.mostOptimizedSort(copy);
//
System.out.println(Arrays.toString(bubbleSort.mostOptimizedSort(copy)));
}
} Wnioski:
O ile w mniejszych zbiorach danych nie widać szczególnej różnicy między Optymized i SuperOptimized to w przypadku większych zbiorów różnice są zauważalne.
Dla 100_000 elementów wyniki przedstawiają się u mnie następująco:
Number of comparisions (most optimized): 704632143
Time in millis for runnable most-optimized: 50785
Number of comparisions (optimized): 704948251
Time in millis for runnable optimized: 51876
Number of comparisions (non optimized): 1409865409
Time in millis for runnable non-sorted: 96376
Widać więc ile porównań było w najmniej optymalnej wersji, jest to cały rząd wielkości więcej porównań. Algorytmy optymalne różnią się o 316_108 porównań, to dość sporo, choć czasowo to tylko około sekunda różnicy.
Algorytm bąbelkowy nie może wydajny ale ma fajną nazwę, do tego jest dość prosty w implementacji, więc można go łatwo przyswoić.
Linki z których korzystałem:
http://www.algorytm.org/algorytmy-sortowania/sortowanie-babelkowe-bubblesort/bubble-3-j.html
https://stackoverflow.com/questions/27639792/java-implementation-of-bubble-sort-in-functional-style
