Moderators NEFERPITOU Postat Decembrie 1 Moderators Postat Decembrie 1 ** Bubble Sort ** Bubble Sort sau Sortare cu Bule , este similara cu cea de selectie doar ca se compara vecinii intre ei . Consta in doua bucle iar algoritmul ia sfarsit cand nu mai exista interschimbari . ** Interpretare ** Avem o colectie cu 6 elemente : [4 , 55 , 22, 67 , 89, 90] --> valori [0 , 1 , 2 , 3, 4 ,5 ] --> indecsi Sa presupunem ca cerem sa o ordonam descrescator !!! La prima indexare : i = 0 1. 4 < 55 ==> 4 mai mic decat 55 --> efectuam interschimbare : [55,4,22,67,89,90] ; 2. 4 < 22 ==> 4 mai mic decat 22 --> efectuam interschimbare : [55,22,4,67,89,90] ; 3. 4 < 67 ==> 4 mai mic decat 67 --> efectuam interschimbare : [55,22,67,4,89,90] ; 4. 4 < 89 ==> 4 mai mic decat 89 --> efectuam interschimbare : [55,22,67,89,4,90] ; 5. 4 < 90 ==> 4 mai mic decat 90 --> efectuam interschimbare : [55,22,67,89,90,4] ; La a doua indexare : i = 1; 1. 55 > 22 ==> 55 mai mare decat 22 --> continuam ; 2. 22 < 67 ==> 22 mai mic decat 67 --> efectuam interschimbare : [55,67,22,89,90,4] ; 3. 22 < 89 ==> 22 mai mic decat 89 --> efectuam interschimbare : [55,67,89,22,90,4] ; 4. 22 < 90 ==> 22 mai mic decat 90 --> efectuam interschimbare : [55,67,89,90,22,4] ; 5. 22 > 4 ==> 22 mai mare decat 4 --> continuam La a treia indexare : i = 2 ; 1. 55 < 67 ==> 67 mai mare decat 55 --> efectuam interschimbare : [67,55,89,90,22,4] ; 2. 55 < 89 ==> 55 mai mic decat 89 --> efectuam interschimbare : [67,89,55,90,22,4] ; 3. 55 < 90 ==> 55 mai mic decat 90 --> efectuam interschimbare : [67,89,90,55,22,4] ; 4. 55 > 22 ==> 55 mai mare decat 22 --> continuam 5. 22 > 4 ==> 22 mai mare decat 4 --> continuam La a patrea iteratie : i = 3 ; 1. 67 < 89 ==> 67 mai mic decat 89 ==> efectuam interschimbare : [89,67,90,55,22,4] ; 2. 67 < 90 ==> 67 mai mic decat 90 ==> efectuam interschimbare : [89,90,67,55,22,4] ; 3. 67 > 55 ==> 67 mai mare decat 55 ==> continuam ; 4. 55 > 22 ==> 55 mai mare decat 22 ==> continuam ; 5. 22 > 4 ==> 22 mai mare decat 4 ==> continuam ; La a cincea iteratie : i = 4 ; 1. 89 < 90 ==> 89 mai mic decat 90 ==> efectuam interschimbare : [90,89,67,55,22,4] ; 2. 89 > 67 ==> 89 mai mare decat 67 ==> continuam ; 3. 67 > 55 ==> 67 mai mare decat 55 ==> continuam ; 4. 55 > 22 ==> 55 mai mare decat 22 ==> continuam ; 5. 22 > 4 ==> 22 mai mare decat 4 ==> continuam ; La a sasea iteratie : i = 5 ; 1. 90 > 89 ==> 90 mai mare decat 89 ==> continuam ; 2. 89 > 67 ==> 89 mai mare decat 67 ==> continuam ; 3. 67 > 55 ==> 67 mai mare decat 55 ==> continuam ; 4. 55 > 22 ==> 55 mai mare decat 22 ==> continuam ; 5. 22 > 4 ==> 22 mai mare decat 4 ==> continuam ; ==> NIMIC DE INTERSCHIMBAT ==> SFARSIT ALGORITM NOTA ** : Daca dorim ordine crescatoare , doar inversam comparatiile !! ** Interpretare cod C ** #include <stdio.h> #include <stdlib.h> // Pentru malloc & free int* bubbleSort(int *arr,int bufferArray) { int stillUnordered = 0; // Valoare 0 (Nu exista bool in C) for (int i = 0; i < bufferArray - 1; i++) { for (int j = 0; j < (bufferArray-i-1); j++) { if (arr[j] < arr[j + 1]) // "<" pentru descrescator si ">" pentru crescator { // Efectuam Interschimbarea int temp = arr[j]; arr[j] = arr[j + 1]; // Arr[j+1] ii va lua locul lu arr[j] arr[j + 1] = temp; // Valoarea mai mica o ducem mai in spate stillUnordered = 1; } } if (stillUnordered != 1) // Algoritmul s-a finalizat { break; // Nu mai e necesar sa rulam tot loopul } } return arr; // Returnam colectia ordonata } int main() { int arrayBuffer; printf("Cate numere doresti sa aiba colectia : "); scanf_s("%d", &arrayBuffer); int* a = (int*)malloc(arrayBuffer * sizeof(int)); // ALOCAM UN ARRAY IN FUNCTIE DE CATE NUMERE VREA UTILIZATORUL SA INTRODUCA printf("Insereaza %d numere la intamplare : \n",arrayBuffer); for (int i = 0; i < arrayBuffer; i++) { printf("colectie[%d] = ", i); scanf_s("%d", &a[i]); // Inseram numerele de la tastatura } a = bubbleSort(a,arrayBuffer); // Transferam colectia prin valoare si rezultatul o egalam cu a /// Printam Colectia printf("Printam colectia ordonata : \n"); for (int i = 0; i < arrayBuffer; i++) { printf("v[%d]=%d\n", i, a[i]); } // Eliberam Memoria Ocupata de Array (Sa prevenim Memory Leak) free(a); // Eliberam Colectia in sine a = NULL; // Setam NULL Pointer return 0; } NOTA 1 ** : ALGORITM USOR DE IMPLEMENTAT SI INTELES !! NOTA 2 ** : CU CAT COLECTIA E MAI MARE CU ATAT ALGORITMUL DEVINE MAI INEFICIENT (Timp de Executie mai mare ) ; NOTA 3 ** : DIN PRICINA NUMEROASELOR COMPARATII , SE PREFERA ALGORITMUL DE SELECTIE IN DEFAVOAREA ACESTUIA !!
Postări Recomandate