Buna ziua doamnelor si domnilor si bine v-am regasit. Ma numesc Zero Davila, iar astazi vom invata un algoritm de sortare lent denumit Bubble Sort si il vom implementa in java, explicand codul la fiecare pas, bineinteles. Am creat si reprezentari ascii pentru cateva algoritme pentru a va fi mai usor sa vizualizati ce se intampla. Deci avem un array nesortat de 7 elemente. Iar algoritmul va incepe cu primele 2 elemente. Daca elementul din stanga va fi mai mare decat cel din dreapta, atunci elementele vor fi inversate. Daca nu atunci algoritmul va continua cu urmatoarele elemente si anume pozitiile 1 si 2, fiindca indexarea elementelor nu incepe de la 1 ci de la 0, deci primele doua
elemente aveau indexii 0 si 1. Procesul va decurge in mai multe etape. Dupa prima etapa cel mai mare numar va ajunge in extrema dreapta, iar pentru eficienta, pentru urmatoarea etapa recursiva ultimul element va fi ignorat. Procesul va fi repetat pana cand tot array-ul va fi sortat in ordine crescatoare, iar numarul de etape recursive va depinde de numarul de elemente.
public class MyBubbleSort {
public static void bubble_srt(int array[]) {
int n = array.length;
int k;
for (int m = n; m >= 0; m–) {
for (int i = 0; i < n – 1; i++) {
k = i + 1;
if (array[i] > array[k]) {
swapNumbers(i, k, array);
}
}
printNumbers(array);
}
}
private static void swapNumbers(int i, int j, int[] array) {
int temp;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static void printNumbers(int[] input) {
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + „, „);
}
System.out.println(„\n”);
}
public static void main(String[] args) {
int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
bubble_srt(input);
}
}
Algoritm de sortare Bubble Sort.
ARRAY NESORTAT
____________________________________
| | | | | | | |
| 8 | 3 | 5 | 1 | 6 | 7 | 9 |
|____|____|____|____|____|____|____|
index 0 1 2 3 4 5 6
____________________________________________
| ETAPA I
| ____________________________________
| | | | | | | | |
| | 8 | 3 | 5 | 1 | 6 | 7 | 9 |
| |____|____|____|____|____|____|____|
| | 8 > 3 |
| | (schimb)|
| ____________________________________
| | | | | | | | |
| | 3 | 8 | 5 | 1 | 6 | 7 | 9 |
| |x___|____|____|____|____|____|____|
| | 8 > 5 |
| | (schimb)|
| ____________________________________
| | | | | | | | |
| | 3 | 5 | 8 | 1 | 6 | 7 | 9 |
| |x___|x___|____|____|____|____|____|
| | 8 > 1 |
| | (schimb)|
| ____________________________________
| | | | | | | | |
| | 3 | 5 | 1 | 8 | 6 | 7 | 9 |
| |x___|x___|x___|____|____|____|____|
| | 8 > 6 |
| | (schimb |
| ____________________________________
| | | | | | | | |
| | 3 | 5 | 1 | 6 | 8 | 7 | 9 |
| |x___|x___|x___|x___|____|____|____|
| | 8 > 7 |
| | (schimb)|
| ____________________________________
| | | | | | | | |
| | 3 | 5 | 1 | 6 | 7 | 8 | 9 |
| |x___|x___|x___|x___|x___|____|____|
| | 8 < 9 |
| | (ramane)|
|___________________________________________
____________________________________________
| ETAPA A II-a
| ____________________________________
| | | | | | | | |
| | 3 | 5 | 1 | 6 | 7 | 8 | 9 |
| |____|____|____|____|____|____|____|
| | 3 < 5 |
| | (ramane)|
| ____________________________________
| | | | | | | | |
| | 3 | 5 | 1 | 6 | 7 | 8 | 9 |
| |x___|____|____|____|____|____|____|
| | 5 > 1 |
| | (schimb)|
| ____________________________________
| | | | | | | | |
| | 3 | 1 | 5 | 6 | 7 | 8 | 9 |
| |x___|x___|____|____|____|____|____|
| | 5 < 6 |
| | (ramane)|
| ____________________________________
| | | | | | | | |
| | 3 | 1 | 5 | 6 | 7 | 8 | 9 |
| |x___|x___|x___|____|____|____|____|
| | 6 > 7 |
| | (ramane)|
| ____________________________________
| | | | | | | | |
| | 3 | 1 | 5 | 6 | 7 | 8 | 9 |
| |x___|x___|x___|x___|____|____|____|
| | 7 < 8 |
| | (ramane)|
|__________________________________________
___________________________________________
| ETAPA A III-a
| ____________________________________
| | | | | | | | |
| | 3 | 1 | 5 | 6 | 7 | 8 | 9 |
| |____|____|____|____|____|____|____|
| | 3 > 1 |
| | (schimb)|
| ____________________________________
| | | | | | | | |
| | 1 | 3 | 5 | 6 | 7 | 8 | 9 |
| |x___|____|____|____|____|____|____|
| | 3 < 5 |
| | (ramane)|
| ____________________________________
| | | | | | | | |
| | 1 | 3 | 5 | 6 | 7 | 8 | 9 |
| |x___|x___|____|____|____|____|____|
| | 5 < 6 |
| | (ramane)|
|
| ____________________________________
| | | | | | | | |
| | 1 | 3 | 5 | 6 | 7 | 8 | 9 |
| |x___|x___|x___|____|____|____|____|
| | 6 < 7 |
| | (ramane)|
|__________________________________________
___________________________________________
| ETAPA A IV-a
| ____________________________________
| | | | | | | | |
| | 1 | 3 | 5 | 6 | 7 | 8 | 9 |
| |____|____|____|____|____|____|____|
| | 1 < 3 |
| | (ramane)|
| ____________________________________
| | | | | | | | |
| | 1 | 3 | 5 | 6 | 7 | 8 | 9 |
| |x___|____|____|____|____|____|____|
| | 3 < 5 |
| | (ramane)|
| ____________________________________
| | | | | | | | |
| | 1 | 3 | 5 | 6 | 7 | 8 | 9 |
| |x___|x___|____|____|____|____|____|
| | 5 < 6 |
| | (ramane)|
|__________________________________________
___________________________________________
| ETAPA A V-a
| ____________________________________
| | | | | | | | |
| | 1 | 3 | 5 | 6 | 7 | 8 | 9 |
| |____|____|____|____|____|____|____|
| | 1 < 3 |
| | (ramane)|
| ____________________________________
| | | | | | | | |
| | 1 | 3 | 5 | 6 | 7 | 8 | 9 |
| |x___|____|____|____|____|____|____|
| | 3 < 5 |
| | (ramane)|
|__________________________________________
___________________________________________
| ETAPA A VI-a
| ____________________________________
| | | | | | | | |
| | 1 | 3 | 5 | 6 | 7 | 8 | 9 |
| |____|____|____|____|____|____|____|
| | 1 < 3 |
| | (ramane)|
|__________________________________________
ARRAY SORTAT
____________________________________
| | | | | | | |
| 1 | 3 | 5 | 6 | 7 | 8 | 9 |
|____|____|____|____|____|____|____|
index 0 1 2 3 4 5 6