O mojí osobě

Něco ke stažení

Články a návody

Poezie

Odkazy

Bubble sort



Bubble sort, neboli bublinkové třídění, patří k nejjednodušším algoritmům na setřídění posloupnosti prvků. Při třídění prochází vstupní prvky, vždy dva sousední porovnává a v případě potřeby prohazuje. Protože po prvním průchodu se nám na poslední pozici dostane prvek, který je největší (nebo nejmenší, podle směru třídění) a už s ním nebudeme hýbat, nemusíme již tento prvek v příštím průchodu testovat a po každém průchodu se nám tedy o jeden prvek zmenší posloupnost prvků nesetříděných. Pokud při jednom průchodu nedojde ani k jednomu prohození prvků, je již posloupnost setříděná a algoritmus ukončíme.

Existuje i několik modifikací tohoto základního algoritmu, například obousměrný Bubblesort - ten střídá průchody posloupností zleva doprava a zprava doleva, takže na začátku se hromadí prvky nejmenší a na konci prvky největší.

Algoritmus Bubblesort má časovou složitost O(n^2), takže se pro běžné třídění nepoužívá. Lze ho ale velmi dobře použít pro třídění v některých speciálních případech kdy dochází jen k malému počtu prohození prvků, neboť pro setřídění již utříděné posloupnosti potřebuje čas pouze O(n). Jeho další výhodou je nenáročnost na paměť - pro provedení třídění si vystačíme pouze s pamětí, kterou zabírají vstupní prvky a nepotřebujeme žádnou další pracovní paměť ani zásobníky.

Příklad setřídění pole prvků typu float: 

void BubbleSort(float *pole)
{
int delka,i,j,flip;
float pomocny;


//tady se mi spocte delka pole
delka=Spocti_delku(pole);

for (i=delka; i>0; i--) 
     {
     flip=0;	// tohle je pocitadlo, jestli probehla vymena
     for (j=1;jpole[j]) 
		{	
		// prohodime prvky a zvysime pocitadlo
		pomocny=pole[j];
		pole[j]=pole[j-1];
		polo[j-1]=pomocny;
		flip++;			
		};
	};	
     if (flip==0) break;	
	//neprobehla vymena => jsme hotovi
     };
return;
};

Zpět na index