Bubblesort - třídící algoritmus

Obsah lekce:

Bubblesort - varianta 3

Třetí verze: Třetí verze je ještě optimalizovanější díky absenci všech zmíněných neduh z verzí předchozích.

WHILE

První cyklus FOR byl nahrazen cyklem WHILE, který nám umožní měnit čítač a pomocí libovolné podmínky ovlivňovat počet kroku cyklu (cyklus FOR má v některých jazycích tu vlastnost, že v něm nelze měnit čítač cyklu a FOR tedy musí proběhnout nutně zadaný počet kroků – cyklus WHILE je tedy daleko obecnější a ovladatelnější). Protože základní verze jazyka C, nepodporuje použití logické proměnné typu boolean (jako například v jazyce Pascal), tak pro uchování logické hodnoty použijeme celočíselnou hodnotu, do které budeme ukládat 0 (pro hodnotu false) nebo 1 (pro hodnotu true). Před cyklem WHILE tedy nastavíme proměnnou „s“ (seřazeno) na hodnotu 0 (s=0;), abychom cyklus vůbec spustili. Hned za BEGIN předpokládáme, že jsou čísla seřazena a nastavíme tedy s=1; tímto krokem ošetříme případ, kdy už jsou čísla seřazena. Pokud tedy ale nejsou, tak se nám už ve známé podmínce if (p[i]>p[i+1]) {...} změní proměnná „s“ zpět na 0 (s=0) a v tom případě se cyklus WHILE zopakuje. Pokud by čísla seřazená už byla (nebo se tak stalo např.: po druhém průchodu celým cyklem), cyklus WHILE se už opakovat nebude, neboť podmínka IF už platná není a tudíž zůstane s=1.

Rozdíl mezi pmax-1 a pmax-k

Princip schodů ošetříme stejně jako ve druhé verzi v cyklu for (i=0; i < pmax-k; i++). Zde je ale ještě důležité, aby se před samotným cyklem WHILE proměnná „k“ nastavila na hodnotu 0 (tedy k=0), neboť kdyby tento řádek neuvedli, tak program nebude fungovat vůbec - k by nemělo nastaveno žádnou výchozí hodnotu. Také tam nemůže být třeba dvojka, trojka či pětka, neboť bychom se při prvním průchodu cyklem FOR nedostali na konec pole. Dále je nutné, aby se na konci cyklu WHILE (předtím než se cyklus zopakuje) hodnota „k“ zvedla o jedna (k=k+1), díky tomu bude fungovat „princip schodů“. Optimalizovali jsme některé možnosti, které mohou vzniknout při seřazování a tím zredukovali počet průchodů cyklem, což má za následek rychlejší běh.

Jako ukázku uvedeme následující graf. V něm jsou uvedeny hodnoty pro pmax=1000, které ukazují množství průchodů cyklem (tedy jakoby počet řádků) a množství porovnávaných čísel.

Bubblesort - varianta 4 - poslední optimalizace

Poslední optimalizace přináší zrychlení řazení. Tato varianta dělá právě to, že při prvním průchodu cyklem WHILE máme největší číslo na konci a nejmenší na začátku. V každém dalším kroku se už porovnávají čísla v rozmezí 0+k až pmax-k, kdy k se při každém průchodu cyklem zvětšuje o jedno. Schéma vypadá jako převrácená pyramida.

Pro srovnání s předešlými verzemi uvádíme další graf:

Zdrojový kód použitý k porovnání rychlosti variant optimalizace

#include "stdafx.h"
#include <stdlib.h>
#include <time.h>

#define pmax 1000

int _tmain(int argc, _TCHAR* argv[])
{
	int p[pmax], pz[pmax];
	int s, pocetk, poceti, opakovani;
	int i, k;

	srand((unsigned int) time(NULL));

	opakovani = 0;

	while (opakovani < 10)
	{
		for (i = 0; i < pmax; i++)
		{
			p[i] = rand()%3000;
		}

		for (i = 0; i < pmax; i++)
		{
			pz[i] = p[i];
		}

		// start neoptimalizovane bez K
		pocetk = 0;
		poceti = 0;

		for (k = 0; k < pmax-1; k++)
		{
			for (i = 0; i < pmax-1; i++)
			{
				if (p[i]>p[i+1])
				{
					int pom = p[i];
					p[i] = p[i+1];
					p[i+1] = pom;
				}
				poceti = poceti + 1;
			}
			pocetk = pocetk + 1;
		}
		printf("Pocet K neop: %d\n", pocetk);
		printf("Pocet I neop: %d\n", poceti);

		//konec neoptimalizovane bez K}
		//start neoptimalizovane s K}
		for (i = 0; i < pmax; i++)
		{
			p[i] = pz[i];
		}
		pocetk = 0;
		poceti = 0;

		for (k = 0; k < pmax-1; k++)
		{
			for (i = 0; i < pmax-k-1; i++)
			{
				if (p[i]>p[i+1])
				{
					int pom = p[i];
					p[i] = p[i+1];
					p[i+1] = pom;
				}
				poceti = poceti + 1;
			}
			pocetk = pocetk + 1;
		}
		printf("Pocet K (s K): %d\n", pocetk);
		printf("Pocet I (s K): %d\n", poceti);
	
		//konec neoptimalizovane s K
		//start optimalizovane
		for (i = 0; i < pmax; i++)
		{
			p[i] = pz[i];
		}
		k = 0;
		pocetk = 0;
		poceti = 0;
		s = 0;

		while (s == 0)
		{
			s = 1;
			for (i = 0; i < pmax - k -1; i++)
			{
				if (p[i]>p[i+1])
				{
					int pom = p[i];
					p[i] = p[i+1];
					p[i+1] = pom;
					s = 0;
				}
				poceti = poceti + 1;
			}
			k = k+1;
			pocetk = pocetk + 1;
		}
		printf("Pocet K optimal: %d\n", pocetk);
		printf("Pocet I optimal: %d\n", poceti);
		//konec optimalizovane
		//start optimalizovane 2
		for (i = 0; i < pmax; i++)
		{
			p[i] = pz[i];
		}
		k = 0;
		pocetk = 0;
		poceti = 0;
		s = 0;

		while (s == 0)
		{
			s = 1;
			for (i = 0+k; i < pmax-k -1; i++)
			{
				if (p[i]>p[i+1])
				{
					int pom = p[i];
					p[i] = p[i+1];
					p[i+1] = pom;
					s = 0;
				}
				poceti = poceti + 1;
			}

			for (i = pmax-k-1; i > 1+k; i--)
			{
				if (p[i]<p[i-1])
				{
					int pom = p[i];
					p[i] = p[i-1];
					p[i-1] = pom;
					s = 0;
				}
				poceti = poceti + 1;
			}

			k=k+1;
			pocetk=pocetk+2;
		}

		printf("Pocet K optimal2: %d\n",pocetk);
		printf("Pocet I optimal2: %d\n",poceti);
		// konec optimalizovane 2
		opakovani=opakovani+1;
		printf("Pocet kompletniho cyklu %d\n",opakovani);
		printf("\n");
	}
	fflush(stdin);
	getchar();
	return 0;
}

Domácí úkol

Nalezněte na Internetu alespoň dva další algoritmy na třídění čísel a jeden realizujte v jazyce C.

Otázky

1. Popište princip algoritmu Bubblesort.
2. Jaké optimalizace lze v algoritmu Bubblesort realizovat?
3. Uveďte alespoň dva další příklady třídících algoritmů.