Szükséges előismeret: Függvények aszimptotikus viselkedése, Jelölések, Buborékrendezés

Algoritmusok és adatszerkezetek 1. > Egyszerű rendezések > Javított buborékrendezés

Javított buborékrendezés (Improved bubble sort)

Egy csere valójában 3 mozgatást jelent, így a buborékrendezés szükségtelenül sok mozgatást hajt végre. Ezen próbálunk meg javítani.

Az első ötlet az, hogy egy logikai változó segítségével figyeljük, hogy volt-e csere. Ha nem történt csere az azt jelenti, hogy rendezett a tömbünk, ezért leállhat a külső ciklus. A második ötlet az, hogy jegyezzük meg az utolsó csere helyét. Az utolsó csere mögötti résztömb már rendezett lesz, ezért a külső ciklusnak már csak az utolsó cseréig kell mennie. Addig megy a külső ciklus, amíg az utolsó csere nem a tömb elején történt. Ennek a megvalósítását láthatjuk itt.

Műveletigény:

$MT(n) \in \Theta(n^2)$
$mT(n) \in \Theta(n)$

Gyakorlati alkalmazása:

Ugyanúgy, mint a buborékrendezés ez is egy könnyen implementálható rendező algoritmus, ezért ha valakinek kevés elemet kell rendeznie és nem számít a hatékonyság, lehet, hogy ezt fogja használni.

Animáció

Struktogram

$ImprovedBubbleSort(A:T[n])$

$i := n-1$
	$i \geq 1$
	$u := -1$
		$j := 0 \space to \space i-1$
		$A[j] > A[j+1]$
		$swap(A[j], A[j+1])$	$\text{SKIP}$
		$u := j$
	$i := u$

Animáció

Struktogram

$ImprovedBubbleSort(A:T[n])$

$i := n-1$
	$i \geq 1$
	$u := -1$
		$j := 0 \space to \space i-1$
		$A[j] > A[j+1]$
		$swap(A[j], A[j+1])$	$\text{SKIP}$
		$u := j$
	$i := u$

Feladatok

Az alábbi feladatok a gyakorlatokon elvégzendő kötelező, illetve gyakorló feladatok.