Třídění

Píšete tělo funkce, která dostane jeden parametr – pole, které má utřídit. Pole máte vrátit utříděné, anebo nevrátit nic a pole rovnou utřídit na místě.

Oproti klasickému Javascriptu dostáváte jako dárek funkci pole.swap(i, j). Prohodí dva prvky na zadaných pozicích, pro třídění je dost užitečná. Pohodlí může snad pomoct i to, že funkce navrací svůj druhý parametr, j.

Počet prvků:
function setrid(pole) {

}

Čas:
Vstup:
Výstup:

Bublinkové třídění

Procházíme pole pokaždé od začátku a kdykoliv potkáme dvě hodnoty ve špatném pořadí, prohodíme je.

var musime_pokracovat = true;
while (musime_pokracovat) {
	musime_pokracovat = false;
	for (var i=1; i<pole.length; i++) {
		if (pole[i-1] > pole[i]) {
			pole.swap(i, i-1);
			musime_pokracovat = true;
		}
	}
}

Přímý výběr

Pokaždé najdeme nejmenší hodnotu ve zbytku pole a dáme ji na konec výstupu. Díky pečlivému plánování si vystačíme s původním polem, bez kopírování.

for (var i=0; i<pole.length - 1; i++) {
	var min = i;
	for (var j=i+1; j<pole.length; j++) {
		if (pole[j] < pole[min]) {
			min = j;
		}
	}
	pole.swap(i, min);
}

Přímé vkládání

Každou hodnotu posuneme doleva až na místo, kam patří. Díky tomu vystačíme s jedním polem (normálně bychom měli začít s prázdným polem a do něj přidávat).

for (var i=1; i<pole.length; i++) {
	var hodnota = pole[i];
	for (var cil=0; pole[cil] < hodnota; cil++) {
	}
	for (var j=i; j > cil; --j) {
		pole[j] = pole[j - 1];
	}
	pole[cil] = hodnota;
}

Třídění sléváním

Slévání spojí dvě utříděná pole do jednoho. Pole rozdělíme vejpůl, utřídíme obě poloviny rekurzivně a pak je sléváním spojíme dohromady. Rekurze končí u pole délky 1.

function merge(a, b) {
	var ia = 0, ib = 0;
	var vysledek = [];
	while (ia < a.length && ib < b.length) {
		if (a[ia] < b[ib]) {
			vysledek.push(a[ia]);
			ia += 1;
		} else {
			vysledek.push(b[ib]);
			ib += 1;
		}
	}
	while (ia < a.length) {
		vysledek.push(a[ia]);
		ia += 1;
	}
	while (ib < b.length) {
		vysledek.push(b[ib]);
		ib += 1;
	}
	return vysledek;
}

function mergesort(a) {
	if (a.length <= 1) {
		return a;
	}
	var pulka = Math.floor(a.length / 2);
	var levy = a.slice(0, pulka);
	var pravy = a.slice(pulka, a.length);
    return merge(mergesort(levy), mergesort(pravy));
}

return mergesort(pole);

Quicksort

Vybereme si nějakou prahovou hodnotu, může to být třeba první hodnota v poli. Pole pak rozdělíme na dvě části: do jedné dáme hodnoty menší než práh, do druhé větší. Ujistíme se, že v obou částech je aspoň jeden prvek – přesný způsob záleží na tom, jak vybíráme prahovou hodnotu. Pak obě pole utřídíme rekurzivně a spojíme je za sebe. Kód se dá napsat stručně:

function quicksort(pole) {
	if (pole.length <= 1)
		return pole;
	var hranice = pole[0], mensi = [], vetsi = [];
	for (var prvek of pole)
		((prvek < hranice) ? mensi : vetsi).push(prvek);
	if (mensi.length == 0)
		return [pole[0]].concat(quicksort(pole.slice(1)));
	else
		return quicksort(mensi).concat(quicksort(vetsi));
}

return quicksort(pole);
A teď doopravdy. Quicksort je náramně rychlý algoritmus, ale určitě se chceme vyhnout kopírování polí sem a tam. Rozepíšeme tedy podrobně funkci partition, která přesype menší hodnoty na začátek pole.

function partition(pole, prah, levy, pravy) {
	while (1) {
		while (pole[levy] < prah) {
			levy += 1;
		}
		do {
			pravy -= 1;
		} while (pole[pravy] >= prah);
		if (levy < pravy) {
			pole.swap(levy, pravy);
		} else {
			return levy;
		}
	}
}

function quicksort(pole, zacatek, konec) {
	if (konec - zacatek > 1) {
		var prah = pole[zacatek];
		var rozhrani = partition(pole, prah, zacatek + 1, konec);
		pole.swap(zacatek, rozhrani - 1);
		quicksort(pole, zacatek, rozhrani - 1);
		quicksort(pole, rozhrani, konec);
	}
}

quicksort(pole, 0, pole.length);

Třídění haldou

Halda je datová struktura, do které jde přidat prvek anebo z ní největší prvek vyndat. Použijeme binární haldu a s trochou péče ji uložíme do začátku pole, aniž bychom museli něco kopírovat. Postupně do haldy přidáme všechny prvky pole a pak je jeden po druhém vyndáme.

function rodic(i) {
	return Math.floor((i - 1) / 2);
}

function levy_syn(i) {
	return 2 * i + 1;
}

function pravy_syn(i) {
	return 2 * i + 2;
}

for (var delka=0; delka < pole.length; delka++) {
	var novy = delka;
	while (novy > 0 && pole[rodic(novy)] < pole[novy]) {
		pole.swap(novy, rodic(novy));
		novy = rodic(novy);
	}
}
for (var delka = pole.length - 1; delka > 0; delka--) {
	pole.swap(0, delka);
	var novy = 0;
	while (levy_syn(novy) < delka) {
		if (pravy_syn(novy) < delka && pole[pravy_syn(novy)] > pole[levy_syn(novy)] && pole[pravy_syn(novy)] > pole[novy]) {
			pole.swap(novy, pravy_syn(novy));
			novy = pravy_syn(novy);
		} else if (pole[levy_syn(novy)] > pole[novy]) {
			pole.swap(novy, levy_syn(novy));
			novy = levy_syn(novy);
		} else {
			break;
		}
	}
}