Buna ziua doamnelor si domnilor si bine v-am regasit. Ma numesc Zero Davila. A venit randul algoritmului de sortare denumit insertion sort, care intai il vom explica si apoi implementa in Java. Ajuta daca il vizualizam ca elemente pe care le trecem dintr-o mana in alta. Algoritmul incepe prin a lua primul element din mana stanga, si apoi introduce in mana dreapta. Apoi va lua al doilea element din mana stanga si il va introduce in dreapta
ca al doilea element, dar il va compara cu cel anterior, si avand in vedere ca -5 e mai mic decat 1, elementele vor fi schimbate. Va continua tot asa cu al treilea element si toate care vor urma pana cand ramanem cu un array sortat. In cazul nostru al treilea element a fost 8, a fost trecut in dreapta dupa -5 si 1, si avand in vedere ca 8 e mai mare decat 1, si-a mentinut pozitia si nimic nu sa schimbat.
public class MyInsertionSort {
public static void main(String[] args) {
int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
insertionSort(input);
}
public 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 insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j – 1;
while ((i > -1) && (array[i] > key)) {
array[i+1] = array[i];
i–;
}
array[i+1] = key;
printNumbers(array);
}
}
}
Algoritm de sortare Insertion Sort.
ARRAY NESORTAT
_________________________________ _____
| 1 |-5 | 8 | 3 | 4 | 6 | 5 | 9 | | 1 |
|___|___|___|___|___|___|___|___| |___|___|___|___|___|___|___|___|
|_______________________________________|
_________________________________ _________
| X |-5 | 8 | 3 | 4 | 6 | 5 | 9 | |-5 | 1 |
|___|___|___|___|___|___|___|___| |___|___|___|___|___|___|___|___|
|___________________________________|
_________________________________ _____________
| X | X | 8 | 3 | 4 | 6 | 5 | 9 | |-5 | 1 | 8 |
|___|___|___|___|___|___|___|___| |___|___|___|___|___|___|___|___|
|_______________________________________|
_________________________________ _________________
| X | X | X | 3 | 4 | 6 | 5 | 9 | |-5 | 1 | 3 | 8 |
|___|___|___|___|___|___|___|___| |___|___|___|___|___|___|___|___|
|___________________________________|
_________________________________ _____________________
| X | X | X | X | 4 | 6 | 5 | 9 | |-5 | 1 | 3 | 4 | 8 |
|___|___|___|___|___|___|___|___| |___|___|___|___|___|___|___|___|
|___________________________________|
_________________________________ _________________________
| X | X | X | X | X | 6 | 5 | 9 | |-5 | 1 | 3 | 4 | 6 | 8 |
|___|___|___|___|___|___|___|___| |___|___|___|___|___|___|___|___|
|___________________________________|
_________________________________ _____________________________
| X | X | X | X | X | X | 5 | 9 | |-5 | 1 | 3 | 4 | 5 | 6 | 8 |
|___|___|___|___|___|___|___|___| |___|___|___|___|___|___|___|___|
|_______________________________|
_________________________________ _________________________________
| X | X | X | X | X | X | X | 9 | |-5 | 1 | 3 | 4 | 5 | 6 | 8 | 9 |
|___|___|___|___|___|___|___|___| |___|___|___|___|___|___|___|___|
|_______________________________________|
ARRAY SORTAT