Windows ⇒ Algoritmi si Structuri de Date - C] Bubble Sort

[Diliul]

** 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 :

Cod: Selectaţi tot

[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

Cod: Selectaţi tot

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;

Cod: Selectaţi tot

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 ;

Cod: Selectaţi tot

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 ;

Cod: Selectaţi tot

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 ;

Cod: Selectaţi tot

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 ;

Cod: Selectaţi tot

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 **

Cod: Selectaţi tot

#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 !!